A Bug

Link to quiz:

Look at this picture:

I did that answer which I think is the normal runtime but I think because big O means worst case it should be O(n ^ 2). That question is supposed to say not the big O runtime or worst runtime.
In fact, I think that question is a bit like the same as this one:

Which is because it also says the worst case.

I think this may be due to conventions on how O-notation is used. You might know this, in academia, Θ(n) is used to describe the worst-case runtime, O(n) is used to describe an upper bound (i.e. no worse than n) but is not a “tight” descriptor, and finally Ω(n) is used to describe the lower bound.

However, in common usage I’ve seen O used as a substitute for Θ. (I suspect these exercises lean on the common usage).

I think it’s useful to adjust depending on the context for this. Where ease and accuracy of communication are the two primary goals.

There’s even lower-case versions (“little o”, “little omega”, “little theta”) and versions with a tilde Õ(n) (“soft-oh” notation with logartihmic factors ignored). But those are only relevant if you’re interested in algorithms in a specific sense.

1 Like

Tell me more about the lowercase versions and the tilde one.

In what academia?

This is strange, then how do I know which one is which one if I think the oposite?


By academia I mean in university and research settings (for example, research of algorithms and other studies that require analysis asymptotic behavior).

Usually, it’s not an issue to mix it up, because the less formal usage is looser (and therefore safer to have a small margin).

So I’ll preface this by saying that the word is and equals are also often misused. (This is a note that is admitted in books like the MIT Press Introduction to Algorithms, which is a great book by the way). It doesn’t mean it will or should stop soon, and outside of uni it’s better not to be pedantic.

What do I mean by misused? An example: In a strict sense to say a function is O(n) means that it is in the set of O(n) functions (all functions with a loose upper bound of O(n)). So to say my_function = O(n) or my_function is O(n) can’t really be the case… it’s more accurate to say my_function O(n). But also interestingly it means that because it’s a loose upper bound, if it’s O(n), it’s also O(n^2), and O(n!) and O(n^n) and so on.

Why is that useful knowledge? Sometimes you’ll know the equation that your algorithm runs in but you don’t know what it’s bounds are. So one strategy you can use is you can deduce what the wide bounds are as you make more calculations… to get a rough estimate.

An example of this:
T(n) = 2T(n/2) + n

We can see that it’s clearly at least going to be n (because of the linear n at the end of the expression), so we know it’s Ω(n).
Ω(n) <= 2T(n/2) + n <= ???

And If you try plugging in a few values for T, (say, 1-9), you may or may not see a pattern, but you can clearly see it’s under n^2, so that’s a safe upper bound.

Ω(n) <= 2T(n/2) + n <= O(n^2)

This is already a much better starting point for guessing than before! It rules out a lot of things it can be… and even if we only learn this much it’s quite a bit.

It turns out that the function is Θ(n lg n), which can be proven with induction (and this represents the “tight” worst case scenario). But the point was to show that the additional notation might seem over-the-top at first but is pretty useful to analyzing one’s own work and other algorithms to which you might not know properties about (not to mention it helps for understanding written material).

A small list from the same book (again with the strong disclaimer that equality is a potentially misleading thing here):

f(n) = Θ(g(n)) is similar to a = b
f(n) = O(g(n)) is similar to a <= b
f(n) = Θ(g(n)) is similar to a >= b
f(n) = o(g(n)) is similar to a < b (this is the little-oh)
f(n) = ω(g(n)) is similar to a > b (this is little-omega)

So a lot of algorithms will have very similar run-times and then the question becomes, are they the same? Which one to pick? A big factor in these choices is contextual. Certain shapes of inputs will mean that the edge case or average case behavior behaves differently.

Hope this helps! Book writers and educators have to balance a very fine-line between density and pragmatism for this material, and different audiences will have different needs.

Not really, I don’t understand what you mean in your post.