CODEWITHSUNDEEP
algorithmmathbig-o
GiBiT
GiBiT

Reputation: 321

Handling 1/2^n when determining big-O runtime?

I have to find the big-O Notation of the following expression:

2n + n(logn)10 + (1/2)n

If I ignore the coefficients, I get 2n + n (log n)10 plus some term involving 1/2. If I ignore the coefficients, I completely lose the last term, but it doesn't seem right to include them.

How should I handle the (1/2)n term?

Upvotes: 0

Views: 157

Answers (2)

arshajii
arshajii

Reputation: 129477

For large n, (1/2)n approaches 0 and becomes negligible. Also, 2n eventually becomes negligible compared to n(logn)10, since the latter grows faster.

Comparing n(logn)10 to 2n is equivalent to comparing (logn)10 to 2 (since both contain a factor of n). Clearly, (logn)10 will surpass 2 for large enough ns -- actually all it takes is an n of 3. As n grows further, the difference between these two terms will increase as well and the significance of the 2n term will become smaller and smaller.

Therefore, the big O expression we're left with is 

O(n(logn)10)

Upvotes: 5

templatetypedef
templatetypedef

Reputation: 372684

Think about what happens to (1/2)n as n gets large. This term gets smaller and smaller and smaller and eventually becomes completely negligible. (In fact, if you pick n = 30, it's smaller than 1 / 1,000,000,000.) One useful observation is that (1/2)n) is never greater than 1/2, so you could note that

2n + n(log n)10 + (1/2)n ≤ 2n + n(log n)10 + 1/2

From there, you can see that this is O(n (log n)10), since the n (log n)10 term grows faster than the 2n term.

Normally, though, you have to be careful with exponentials. Anything of the form an for a > 1 will grow faster than any polynomial, so normally you would drop the polynomials and leave the exponential. Here, you do the opposite.

Hope this helps!

Upvotes: 5

Related Questions