Help with big O notation

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, wo开发者_如何转开发uldn'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).

---

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).

---

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)

---

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.