<h2>Short answer</h2>
<p>Asymptotic analysis — of which <span class="math-container">$O$</span> is the most (over)used 'operator' — does not 'measure performance', instead it provides sophisticated math tools to talk about performance at multiple levels of 'coarseness', usually called 'abstractions'.</p>
<p>Need to start by saying your 'equation'<br />
<span class="math-container">$f(algorithm)=f(g)=O(something)$</span><br />
looks garbled. Could you give the exact form with context in the book/reference you're following?<br />
Anyways for now...</p>
<h2>Some clarifying comments</h2>
<ol>
<li>The symbol '<span class="math-container">$=$</span>' is an abuse of notation and is inconsistent with normal math usage (not to mention assignment in imperative programming).<br />
eg. say we have <span class="math-container">$n = O(n^{3})$</span>.<br />
The precise form would use '<span class="math-container">$\in$</span>'<br />
ie.
<span class="math-container">$n \in O(n^3)$</span>.<br />
Put differently, a term like <span class="math-container">$O(n^{3})$</span> looks like an expression (function) but in fact it is a family (class, set, ...) of functions.</li>
<li>For that (and other) reasons, big <span class="math-container">$O$</span> is almost always the wrong asymptotic that's (over)used. Mostly one wants big <span class="math-container">$\Theta$</span>. Even small <span class="math-container">$o$</span> is usually more appropriate.</li>
<li>Asymptotic classes like <span class="math-container">$O$</span>, <span class="math-container">$o$</span>, <span class="math-container">$\Theta$</span> don't 'measure performance'. Rather they give a vast pallette of differently coarse families of equivalence classes from which we may choose in order to zoom in or out to make suitably narrow — aka precise — or broad — aka vague — statements.<br />
Note: 'Precise' is not necessarily 'good' because it can be uselessly overdetailed and pernickety.</li>
</ol>
<h1>Example</h1>
<p>Say 2 algorithms both have average case time complexity:
<span class="math-container">$\Theta(n \log n)$</span>.</p>
<p>Still on refinement one may be <span class="math-container">$\Theta(2n \log n)$</span>,<br />
whereas the other,  <span class="math-container">$\Theta(5n \log n)$</span>.</p>
<p>So ignoring the constant factors, they are equivalent, introducing them they differ.</p>
<p>One can continue:<br />
Say on further analysis it turns out to be:</p>
<p><span class="math-container">$\Theta({5 n \log n} + 3)$</span> vs. <span class="math-container">$\Theta(2n\log n + 100)$</span></p>
<p>Now <em>asymptotically</em>, ie as <span class="math-container">$n$</span> gets large, the first will be worse than the second, but if the <span class="math-container">$n$</span> is typically quite small the first would be preferable.</p>
<h2>Summary</h2>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th></th>
<th>Algo1</th>
<th>Algo2</th>
</tr>
</thead>
<tbody>
<tr>
<td><span class="math-container">$\textrm{Identical, too coarse}$</span></td>
<td><span class="math-container">$\Theta(n \log n)$</span></td>
<td><span class="math-container">$\Theta(n \log n)$</span></td>
</tr>
<tr>
<td><span class="math-container">$\textrm{Algo1 better}$</span></td>
<td><span class="math-container">$\Theta(2n \log n)$</span></td>
<td><span class="math-container">$\Theta(5n \log n)$</span></td>
</tr>
<tr>
<td><span class="math-container">$\textrm{Both better &amp; worse}$</span></td>
<td><span class="math-container">$\Theta(2n \log n+100)$</span></td>
<td><span class="math-container">$\Theta(5n \log n + 3)$</span></td>
</tr>
</tbody>
</table>
</div><hr />
<p>Note: See <a href="https://cseducators.stackexchange.com/questions/7955/how-to-teach-algorithm-performances-can-be-measured-as-of/7956#comment21617_7956">comment by Stef</a> that makes my answer more correct</p>

CC BY-SA 4.0
2024-01-18T05:14:25.953Z
The oh(term) is also an abuse of notation. Already outside the context of big O asymptotics such notation is commonly abused when people say f(x) when they mean f when they have abusively defined f by saying f(x)=2x to mean ∀x [x∈X→f(x)=2x] in the context of some understood X. oh(term) is different abusive shorthand. Of course one has to look at the definition of the notation one is using. Since the asker references such definitions I don't know why they are aren't reading them to see what speakers are likely to be sloppily saying. Or why they don't ask speakers for their definitions.
philipxy
CC BY-SA 4.0
2024-01-18T06:35:54.060Z
@philipxy: Well sure! I  thought of mentioning that and in fact start my programming classes with λ-calculus. If that is under ones belt one could rephrase the [classic definition](https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition) in this style O(f) = {g | ...}. Would be intersting to play around, probably too cumbersome to be practical. Much more practical is to realize that actual algo performance typically depends on *multiple* variables. Eg. A graph algo depends on number of vertices and number if edges. Etc etc. those situations, single variable functions are over simplistic
Rushi
CC BY-SA 4.0
2024-01-18T06:43:51.907Z
I mention it because your answer is a good response to the question--"How to learn/teach what does O(n) etc. mean"--but would be greatly improved by further addressing the  abuse of notation involved with oh(term). Indeed your answer uses that abusing notation without explaining what it means. PS I almost mentioned that the term in oh(term) could be taken as a lambda expression, but whether that is helpful/relevant depends on the particular explanation for the whole expression oh(term).
philipxy
CC BY-SA 4.0
2024-01-18T07:01:26.110Z
@philipxy OK in response to ur comments,  I've added a note 1.  Nevertheless the subject is vast. There are many other things to mention in this context. a) Asymptomatics were invented near a century before Knuth etc started using them for algo analysis b) It is meant for machine independent performance analysis. Taken literally this is a barefaced oxymoron. c) it typically reifies space/time optima. But there are zillions (ok dozens) of other parameters to optimize eg. Cache misses, disk spin up/down times, power consumption...
Rushi
CC BY-SA 4.0
2024-01-18T07:06:20.400Z
I think my last comment on a mathy education site was about the same issue of teachers & learners being impeded by abuse of notation not being explicitly explained. Even the response to the comment is still oblivious to abuse of notation, to their being both "standard" generic (predicate logic) & "standard" abusive notations. ... https://matheducators.stackexchange.com/questions/27078/intuition-for-order-of-operations-in-compound-transformations#comment72038_27078
philipxy
CC BY-SA 4.0
2024-01-18T07:10:35.517Z
@philipxy Good luck on educating mathematicians to do math  in a clean consistent and — at least long term — easy manner  . Not my hill to die on
Rushi
CC BY-SA 4.0
2024-01-18T07:19:46.103Z
I don't know why you mention all that stuff in your comment "OK in response ..." because the question is about sloppy vs precise use of terminology & notation. An answer doesn't even have to mention the semantics at all, let alone aspects of "the subject".
philipxy
CC BY-SA 4.0
2024-01-18T07:36:55.617Z
@philipxy The equation I added in note 1 highlights that the OP is quite confused on fundamentals. I don't see this question merely as a question about sloppy vs precise notation even if better notation were to help understanding/highlight confusion. This site isn't very suitable for addressing such. The cs site may be better but would demand more prior legwork. [Heck: I didn't even notice the spell correct made asymptotic into asymptomatic!! I guess it's an asymptomatic spell check ]
Rushi
CC BY-SA 4.0
2024-01-23T10:12:00.643Z
I think $\Theta({5 n \log n} + 3)$ should be replaced by $5 n \log n + 3 + o(1)$ in the answer; otherwise $\Theta({5 n \log n} + 3) = \Theta({2 n \log n} + 100) = \Theta({n \log n})$ (where $=$ really means $=$ and not just $\subseteq$).
Stef
CC BY-SA 4.0
2024-01-23T10:26:15.377Z
Thanks @stef. I actually did notice this paradoxical "equation" but did not want to complicate more. Still I've put a pointer to your comment
Rushi
CC BY-SA 4.0
2024-01-16T05:36:20.973Z
2024-01-23T10:27:57.787Z
2024-01-23T10:27:57.787Z
Rushi
<p>How to learn/teach what does <span class="math-container">$O(n)$</span> etc. means when one measures algorithmic complexity? I mean, if <span class="math-container">$f$</span> is a function in mathematical sense, then <span class="math-container">$O$</span> notation is defined rigorously in the book &quot;Asymptotic Analysis&quot; by J.D. Murray. But sometimes computer science teachers gives an algorithm and says its time complexity is for example <span class="math-container">$O(n)$</span>. But do we need a mathematical function <span class="math-container">$f$</span> that gives a pseudocode as an input and a mathematical function <span class="math-container">$g$</span> as an output and then we say <span class="math-container">$f(algorithm)=f(g)=O(something)$</span>?</p>

CC BY-SA 4.0
2024-01-15T12:18:03.703Z
I don't understand your question. What benefit would your function f add? For most of my students, O is pretty intuitive after just a little practice, so it feels like you're just muddying the waters here
Ben I.
<algorithms>
How to teach algorithm performances can be measured as $O(f)$?
# How to teach algorithm performances can be measured as $O(f)$?

(Asked by: username_0 on 2024-01-15)

How to learn/teach what does $O(n)$ etc. means when one measures algorithmic complexity? I mean, if $f$ is a function in mathematical sense, then $O$ notation is defined rigorously in the book "Asymptotic Analysis" by J.D. Murray. But sometimes computer science teachers gives an algorithm and says its time complexity is for example $O(n)$. But do we need a mathematical function $f$ that gives a pseudocode as an input and a mathematical function $g$ as an output and then we say $f(algorithm)=f(g)=O(something)$?

**Tags:** algorithms

> **Comments:**
> **username_1**: I don't understand your question. What benefit would your function f add? For most of my students, O is pretty intuitive after just a little practice, so it feels like you're just muddying the waters here  

---

## 1 answers

### Answer by username_2 on 2024-01-16. Score: 3

## Short answer

Asymptotic analysis — of which $O$ is the most (over)used 'operator' — does not 'measure performance', instead it provides sophisticated math tools to talk about performance at multiple levels of 'coarseness', usually called 'abstractions'.

Need to start by saying your 'equation'  
$f(algorithm)=f(g)=O(something)$  
looks garbled. Could you give the exact form with context in the book/reference you're following?  
Anyways for now...

## Some clarifying comments

1. The symbol '$=$' is an abuse of notation and is inconsistent with normal math usage (not to mention assignment in imperative programming).  
   eg. say we have $n = O(n^{3})$.  
   The precise form would use '$\in$'  
   ie.
   $n \in O(n^3)$.  
   Put differently, a term like $O(n^{3})$ looks like an expression (function) but in fact it is a family (class, set, ...) of functions.
2. For that (and other) reasons, big $O$ is almost always the wrong asymptotic that's (over)used. Mostly one wants big $\Theta$. Even small $o$ is usually more appropriate.
3. Asymptotic classes like $O$, $o$, $\Theta$ don't 'measure performance'. Rather they give a vast pallette of differently coarse families of equivalence classes from which we may choose in order to zoom in or out to make suitably narrow — aka precise — or broad — aka vague — statements.  
   Note: 'Precise' is not necessarily 'good' because it can be uselessly overdetailed and pernickety.

# Example

Say 2 algorithms both have average case time complexity:
$\Theta(n \log n)$.

Still on refinement one may be $\Theta(2n \log n)$,  
whereas the other, $\Theta(5n \log n)$.

So ignoring the constant factors, they are equivalent, introducing them they differ.

One can continue:  
Say on further analysis it turns out to be:

$\Theta({5 n \log n} + 3)$ vs. $\Theta(2n\log n + 100)$

Now *asymptotically*, ie as $n$ gets large, the first will be worse than the second, but if the $n$ is typically quite small the first would be preferable.

## Summary

|  | Algo1 | Algo2 |
| --- | --- | --- |
| $\textrm{Identical, too coarse}$ | $\Theta(n \log n)$ | $\Theta(n \log n)$ |
| $\textrm{Algo1 better}$ | $\Theta(2n \log n)$ | $\Theta(5n \log n)$ |
| $\textrm{Both better & worse}$ | $\Theta(2n \log n+100)$ | $\Theta(5n \log n + 3)$ |

---

Note: See [comment by username_4](https://cseducators.stackexchange.com/questions/7955/how-to-teach-algorithm-performances-can-be-measured-as-of/7956#comment21617_7956) that makes my answer more correct

> **Comments:**
> **username_3**: The oh(term) is also an abuse of notation. Already outside the context of big O asymptotics such notation is commonly abused when people say f(x) when they mean f when they have abusively defined f by saying f(x)=2x to mean ∀x [x∈X→f(x)=2x] in the context of some understood X. oh(term) is different abusive shorthand. Of course one has to look at the definition of the notation one is using. Since the asker references such definitions I don't know why they are aren't reading them to see what speakers are likely to be sloppily saying. Or why they don't ask speakers for their definitions.  
> **username_2**: @username_3: Well sure! I  thought of mentioning that and in fact start my programming classes with λ-calculus. If that is under ones belt one could rephrase the [classic definition](https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition) in this style O(f) = {g | ...}. Would be intersting to play around, probably too cumbersome to be practical. Much more practical is to realize that actual algo performance typically depends on *multiple* variables. Eg. A graph algo depends on number of vertices and number if edges. Etc etc. those situations, single variable functions are over simplistic  
> **username_3**: I mention it because your answer is a good response to the question--"How to learn/teach what does O(n) etc. mean"--but would be greatly improved by further addressing the  abuse of notation involved with oh(term). Indeed your answer uses that abusing notation without explaining what it means. PS I almost mentioned that the term in oh(term) could be taken as a lambda expression, but whether that is helpful/relevant depends on the particular explanation for the whole expression oh(term).  
> **username_2**: @username_3 OK in response to ur comments,  I've added a note 1.  Nevertheless the subject is vast. There are many other things to mention in this context. a) Asymptomatics were invented near a century before Knuth etc started using them for algo analysis b) It is meant for machine independent performance analysis. Taken literally this is a barefaced oxymoron. c) it typically reifies space/time optima. But there are zillions (ok dozens) of other parameters to optimize eg. Cache misses, disk spin up/down times, power consumption...  
> **username_3**: I think my last comment on a mathy education site was about the same issue of teachers & learners being impeded by abuse of notation not being explicitly explained. Even the response to the comment is still oblivious to abuse of notation, to their being both "standard" generic (predicate logic) & "standard" abusive notations. ... https://matheducators.stackexchange.com/questions/27078/intuition-for-order-of-operations-in-compound-transformations#comment72038_27078  
> **username_2**: @username_3 Good luck on educating mathematicians to do math  in a clean consistent and — at least long term — easy manner  . Not my hill to die on  
> **username_3**: I don't know why you mention all that stuff in your comment "OK in response ..." because the question is about sloppy vs precise use of terminology & notation. An answer doesn't even have to mention the semantics at all, let alone aspects of "the subject".  
> **username_2**: @username_3 The equation I added in note 1 highlights that the OP is quite confused on fundamentals. I don't see this question merely as a question about sloppy vs precise notation even if better notation were to help understanding/highlight confusion. This site isn't very suitable for addressing such. The cs site may be better but would demand more prior legwork. [Heck: I didn't even notice the spell correct made asymptotic into asymptomatic!! I guess it's an asymptomatic spell check ]  
> **username_4**: I think $\Theta({5 n \log n} + 3)$ should be replaced by $5 n \log n + 3 + o(1)$ in the answer; otherwise $\Theta({5 n \log n} + 3) = \Theta({2 n \log n} + 100) = \Theta({n \log n})$ (where $=$ really means $=$ and not just $\subseteq$).  
> **username_2**: Thanks @stef. I actually did notice this paradoxical "equation" but did not want to complicate more. Still I've put a pointer to your comment  

---

