Basic Algorithm Anaysis

Announcements Posted on
Four things that unis think matter more than league tables 08-12-2016
    • Thread Starter
    Offline

    0
    ReputationRep:
    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 φ O(n3)

    Here's what I did:
    • 3n3 + n2 <= c * n3
    • 3n3 + n3<= c * n3
    • 4n3 <= c * n3
    • 4n3 <= 4n3
    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 is very poor at speaking english. I actually went to his office hours today to get some help from him and I can at least come up with correct solutions for the proofs however he does not possess the ability to communicate effectively enough to convey the meaning behind the actual proofs. Instead it's all broken english and pieces of sentences. I'm not making fun of him, he's clearly really intelligent, he just doesn't know English very well.

    I'll post here the solution given by the professor from the home work. So I know that 4n^3 is part of the correct solution. I know I also need to find omega 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 to go from what I have there to the solution given by the professor.

    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.
 
 
 
Write a reply… Reply
Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. Oops, you need to agree to our Ts&Cs to register
  2. Slide to join now Processing…

Updated: October 12, 2016
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

Poll
Do you think you'll achieve your predicted A Level grades?
Useful resources
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Quick reply
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.