Proving big O of statement [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

开发者_运维百科 Improve this question

I am having a hard time proving that n^k is O(2^n) for all k. I tried taking lg2 of both sides and have k*lgn=n, but this is wrong. I am not sure how else I can prove this.

---

To show that n^k is O(2ⁿ), note that

n^k = (2^{lg n})^k = 2^{k lg n}

So now you want to find an n₀ and c such that for all n ≥ n₀,

2^{k lg n} ≤ c 2ⁿ

Now, let's let c = 1 and then consider what happens when n = 2^m for some m. If we do this, we get

2^{k lg n} ≤ c 2ⁿ = 2ⁿ

2^{k lg 2m} ≤ 2^2m

2^km ≤ 2^2m

And, since 2ⁿ is a monotonically-increasing function, this is equivalent to

km ≤ 2^m

Now, let's finish things off. Let's suppose that we let m = max{k, 4}, so k ≤ m. Thus we have that

km ≤ m²

We also have that

m² ≤ 2^m

Since for any m ≥ 4, m² ≤ 2^m, and we've ensured by our choice of m that m = max{k, 4}. Combining this, we get that

km ≤ 2^m

Which is equivalent to what we wanted to show above. Consequently, if we pick any n ≥ 2^m = 2^{max{4, k}}, it will be true that n^k ≤ 2ⁿ. Thus by the formal definition of big-O notation, we get that n^k = O(2ⁿ).

I think this math is right; please let me know if I'm wrong!

Hope this helps!

---

I can't comment yet, so I will make this an answer.

Instead of reducing the equation like you have been trying to do, you should try to find an n0 and a M that satisfy the formal definition of big O notation found here: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition

Something along the lines of n0=M=k might work (I haven't written it out so maybe that doesn't work, thats just to give you an idea)