CODEWITHSUNDEEP
data-structuresbig-o
user3076196
user3076196

Reputation: 33

Big oh notation running time

How do you work this out? do you get c first which is the ratio of the two functions then with the ratio find the range of n ? how can you tell ? please explain i'm really lost, Thanks.

Example 1: Prove that running time T(n) = n^3 + 20n + 1 is O(n^3) Proof: by the Big-Oh definition,

T(n) is O(n^3) if T(n) ≤ c·n^3 for some n ≥ n0 .

Let us check this condition:

if n^3 + 20n + 1 ≤ c·n^3 then 1 + 20/n^2 + 1/n^3 <=c .

Therefore, the Big-Oh condition holds for n ≥ n0 = 1 and c ≥ 22 (= 1 + 20 + 1). Larger values of n0 result in smaller factors c (e.g., for n0 = 10 c ≥ 1.201 and so on) but in any case the above statement is valid.

Upvotes: 2

Views: 189

Answers (1)

wheaties
wheaties

Reputation: 35970

I think the trick you're seeing is that you aren't thinking of LARGE numbers. Hence, let's take a counter example:

   T(n) = n^4 + n

and let's assume that we think it's O(N^3) instead of O(N^4). What you could see is

   c = n + 1/n^2

which means that c, a constant, is actually c(n), a function dependent upon n. Taking N to a really big number shows that no matter what, c == c(n), a function of n, so it can't be O(N^3).

What you want is in the limit as N goes to infinity, everything but a constant remains:

   c = 1 + 1/n^3

Now you can easily say, it is still c(n)! As N gets really, really big 1/n^3 goes to zero. Hence, with very large N in the case of declaring T(n) in O(N^4) time, c == 1 or it is a constant!

Does that help?

Upvotes: 2

Related Questions