Hi,
I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C.
Since the the constant "C" can be any integer > 0, wouldn't this following example be true as well?
Example:
n log n ∈ O(log n)
n log n <= log n * c
Where C is equal to the value of n.
I know that the answer is that n log n ∉ O(log n) but I don't understand how since C can be any constant.
Thanks in advance for your help :D
c is just that, a constant. This means that you can't say "let c be the value of n", because you must choose some c first and then allow the comparison to hold for all n.
In other words, in order for some T(n) to be O(G(n)), there must exist no constant c such that G(n)*c is greater than T(n) for all n.
Thus n log n is not O(log n) because, no matter what constant you choose, n > c will cause n log n to be greater than c log n.
Let me repeat your words.
c can be any constant.
This means that c can not depend on n.
the idea is that the inequality holds for any n and a fixed c. so while you might find a certain c such that n log n < c log n, (namely any c>n), you can easily find other n' for which it doesn't hold (namely n'>c).
In the definition you should determine C just by the T and G themselves. This is what a constant C means. So C should not depend on the input of them. So you can not consider C = n
in the expression n log n, you can't compare the outside n to C, like you are doing. That would be like taking the algrebraic expression x(x+1) and replacing one of the x's with a constant.
In n log n, n is a variable. In the big O expresion, C is a constant.
The value of n depends on the input set, the value of C is fixed.
So yes, if n = 16 and C = 256, it looks like n^2 * lg(n) for a small input set. Now increase the input set to 100,000,000; the value of C stays at 256, you now have 256 * lg (100,000,000)
First of all, if n=C then C is not a constant. And in most real-world algorithms, C is small so the big-O part usually dominates for typical values of n.
But big-O complexity is concerned with the efficiency of an algorithm for large n, especially as n approaches infinity. In other words it tells you the scalability of an algorithm: how well a given algorithm handles a very large or doubled workload.
If you know that n is always small then the big-O complexity is not that important, rather you should focus on the wall-clock time required by the algorithm. Also, if you are choosing between two algorithms that have the same big-O complexity (e.g. O(n log n)), quite often one is better than the other (e.g. random-pivot quicksort generally outperforms a binary heap sort).
Whenever I'm stuck on big-oh, I find it useful to think of it as a competition: I choose a big-oh function (so, in your case, logn) and a constant (c). The important thing is that I have to choose a real value. I usually pick a thousand, just because. Then I have to let my arch-nemesis pick any n he chooses. He typically chooses a billion.
Then I make the comparison.
To finish the example, 10^9*(log(10^9)) is now made clearly much bigger than 1000log(10^9). Thus, I know that the big-oh won't work.