2
$\begingroup$

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)$?

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$
    – Ben I.
    Commented Jan 15 at 12:18

1 Answer 1

3
$\begingroup$

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 Stef that makes my answer more correct

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – philipxy
    Commented Jan 18 at 5:14
  • $\begingroup$ @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 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 $\endgroup$
    – Rushi
    Commented Jan 18 at 6:35
  • $\begingroup$ 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). $\endgroup$
    – philipxy
    Commented Jan 18 at 6:43
  • $\begingroup$ @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... $\endgroup$
    – Rushi
    Commented Jan 18 at 7:01
  • 1
    $\begingroup$ @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 $\endgroup$
    – Rushi
    Commented Jan 18 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.