Q: Proving various runtimes have various big-O complexities? How can I prove the following:


*

*10 n log n ∈ O(2n2)

*n log n + 40 · 2n - 6n ∈ O(2n)
In the first one, I'm using this math:

10 n log n ≤ c · 2n2 
10 n2 ≤ c · 2n2  divide by 2
5 n2 ≤ c · n2

I'm guessing that c = 5 and n0 = 1, but I'm not sure if that's true.
In the second one, I tried to multiply the left hand side by 2n but that didn't end up working. Does anyone have any suggestions?

A: For part (1), you want to prove

10 n log n = O(2n2)

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

log n < n

Therefore, you have that

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

Therefore, you can conclude that 10n log n = O(2n2) because you can choose n0 = 1 and c = 5 and use the formal definition of big-O.
For part (i), you want to prove 

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

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

n log n + 40 · 2n - 6n ≤ n log n + 40 · 2n ≤ 40 · 2n + n2 ≤ 40 · 2n + 2n = 41 · 2n

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