Proving n^2 + 3n^3 is Θ(n^3) for n >= 0

[benarceneaux]

First off I'm studying for an exam tomorrow, this isn't homework. Also, I've already written the proof and verified I've gotten the correct answer. I'm here to ask some questions about the solution that I am not completely confident I understand.

Here's the problem:
Prove that n² + 3n² is Θ(n³)

Here's what I did:

• 3n^3 + n^2 <= c * n^3
• 3n^3 + n^3<= c * n^3
• 4n^3 <= c * n^3
• 4n^3 <= 4n^3

This is for big O(To get Θ I know that I also need to prove that the algorithm is Ω(n3)

My problem is that I'm not sure what it means to do this really. My professor first language clearly is not English. I actually went to his office hours today to get some help from him and he was very helpful one on one and I can come up with correct solutions for the proofs. However, his English is so poor that he is unable to convey the meaning behind what we're doing. Instead it's all broken English or pieces of sentences. I'm not making fun of him, he's very intelligent, it's just very difficult to understand what he's trying to say and no one in class asks him to clarify anything. I suppose because it's a room full of shy geeks : P

I'll post here the solution given by the professor from the home work. See, I know that 4n^3 is part of the correct solution. I know I also need to find Ω[g(n)] but I'll ask that question when I get to it lol. So hopefully someone can tell me WHY my answer is correct and how it is similar to what my professor has given as the correct answer.

Here's the answer from the professor:

We show that n^2 + 3n^3 is O(n^3) because for n >= 0,
n^2 + 3n^3 <= 4n^3
We can take c = 4, N = 0 to obtain our result.

 

[Fightfish]

It's nothing more than a series of inequalities: we know that for $n > 1$, $n^2 < n^3$. So,
$$3n^3 + n^2 < 3n^3 + n^3 = 4 n^3$$
So the complexity scales as the cube of $n$ - that's what the big O notation $\mathcal{O}(n^3)$ means.

But you will and should find that the largest power in the polynomial will be the one that determines the scaling complexity of the algorithm, which makes sense because all the lower powers of $n$ are much smaller. So in general, the complexity is governed by the highest power in the polynomial.

 

[Mark44]

Here's the problem:
Prove that n² + 3n² is Θ(n³)

Surely there's a typo here...