Help with big O notation

2018-06-13 22:47:22

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

链接地址: http://www.djcxy.com/p/39732.html

上一篇: Ω（大

下一篇: 大O符号的帮助