1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Basic Algorithm Analysis

  1. Oct 12, 2016 #1
    • Member advised to use the homework template for posts in the homework sections of PF.
    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 n2 + 3n2 is Θ(n3)

    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.
  2. jcsd
  3. Oct 12, 2016 #2
    It's nothing more than a series of inequalities: we know that for ##n > 1##, ##n^2 < n^3##. So,
    [tex]3n^3 + n^2 < 3n^3 + n^3 = 4 n^3[/tex]
    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.
  4. Oct 12, 2016 #3


    Staff: Mentor

    Surely there's a typo here...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted