Proving various runtimes have various big-O complexities?

How can I prove the following:

1. 10 n log n ∈ O(2n²)

2. n log n + 40 · 2ⁿ - 6n ∈ O(2ⁿ)

In the first one, I'm using this math:

开发者_运维知识库

10 n log n ≤ c · 2n²

10 n² ≤ c · 2n² divide by 2

5 n² ≤ c · n²

I'm guessing that c = 5 and n₀ = 1, but I'm not sure if that's true.

In the second one, I tried to multiply the left hand side by 2ⁿ but that didn't end up working. Does anyone have any suggestions?

---

For part (1), you want to prove

10 n log n = O(2n²)

It might help to note that for any n ≥ 1 that

log n < n

Therefore, you have that

10 n log n ≤ 10 n² = 5(2n²)

Therefore, you can conclude that 10n log n = O(2n²) because you can choose n₀ = 1 and c = 5 and use the formal definition of big-O.

For part (i), you want to prove

n log n + 40 · 2ⁿ - 6n = O(2ⁿ)

One useful fact you might want to use here is that n² ≤ 2ⁿ for any n ≥ 4. Therefore, we get that, whenever n ≥ 4

n log n + 40 · 2ⁿ - 6n ≤ n log n + 40 · 2ⁿ ≤ 40 · 2ⁿ + n² ≤ 40 · 2ⁿ + 2ⁿ = 41 · 2ⁿ

Therefore, if you pick n₀ = 4 and c = 41, you can use the formal definition of big-O to prove that n log n + 40 · 2ⁿ - 6n = O(2ⁿ).

Hope this helps!