To be fair, as Lxr points out below, big O notation is an upper bound on the growth rate of a function, and since 2^N grows faster (asymptotically) than (1.618...)^N, O(Fib(N)) <= O(1.618...^N) <= O(2^N) (with some abuse of notation), and the article is technically correct. You may be thinking of big theta notation, which requires both an upper bound and lower bound.

This example is helpful: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...

You are right. I made a mistake, not thinking through big O vs. theta notation. Thanks.

Technically 1.618^N is still O(2^N) but I agree with your point.

I was about to correct you until I realized you used big-O instead of big-theta notation.

Informally we tend to use big-O to mean big-theta which only adds to the confusion.

Actually we don't use it informally as big-Theta, because big-Theta assumes that the lower and upper bound are asymptotically the same.

For example Quicksort is O(n^2) but Omega(nlogn) it is neither Theta(nlogn) nor Theta(n^2).

You probably meant that informally we just assume that the stated bound is as tight as possible.

> For example Quicksort is O(n^2) but Omega(nlogn) it is neither Theta(nlogn) nor Theta(n^2).

No, this is flat out wrong. Big O is an upper bound on an asymptotic growth rate. Big Omega is a lower bound on the asymptotic growth rate. Big Theta is a tight bound on the asymptotic growth rate. These are independent to the average case, best case, or worst case run time of a given algorithm.

Quicksort has an average run time of Theta(n lg n). Equivalently, its average run time is O(n lg n) and Omega(n lg n). It has a worst case run time of Theta(n^2). Equivalently, its worst case run time is O(n^2) and Omega(n^2).

> Actually we don't use it informally as big-Theta,

Wrong again.

You can state that quicksort has run time O(n^2). The function you're describing with O(n^2) is f : S -> R, where S is the set of input values and R is the set of real numbers, and f(x) is the running time of running quicksort on input value x, and n : S -> N is the size of input value x. The notation O(g(n)) describes the function f in terms of the function n.

That f is in O(g(n)) means there exist constants C and N_0 such that for all x in S, provided that n(x) >= N_0, it is true that |f(x)| <= |C g(n(x))|.

And that f is in Omega(g(n)) means there exist C > 0 and N_0 such that for all x in S, provided that n(x) >= N_0, it is true that |f(x)| >= |C g(n(x))|.

Perhaps it is you that need to be educated.

They are independent only if you explicitly state that you are computing them for best/average/worst case independently. Is it commonly done? Sure. But there is nothing in the definition that forces us to do that.

If the things were as you state would you have any use for Omega and Omicron then? Wouldn't just Theta suffice?

> But there is nothing in the definition that forces us to do that.

That's true. You're right.

> If the things were as you state would you have any use for Omega and Omicron then? Wouldn't just Theta suffice?

Couldn't there be cases where we don't have a known tight asymptotic bound but do have an upper and/or lower bound? And although it's an abuse of notation, you do often see big-O used in place of Theta. From CLRS:

"In the literature, we sometimes find O-notation informally describing asymptotically tight bounds, that is, what we have defined using Theta-notation."

My interpretation is that "O(...)" informally means "Theta(...) in the average/amortized case". In the average case, Quicksort is Theta(n log n).