1. Not finding help here? Sign up for a free 30min 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!

Algorithm Analysis (Big Theta)

  1. Nov 15, 2012 #1
    1. The problem statement, all variables and given/known data
    Here is a pastebin link to my question, it contains an algorithm, my trace of the algorithm, and my question.


    2. Relevant equations
    I am interested in the theta notation for the runtime of an algorithm

    3. The attempt at a solution
    Here is the link
    http://mathb.in/1202

    My thoughts are that the algorithm must run in either n^2 or n lg (n) where lg = log base 2
     
  2. jcsd
  3. Nov 15, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Which of those choices do you think fits better? And why? Think about LARGE n.
     
  4. Nov 15, 2012 #3
    n^2 definitely.

    I guess what threw me was the floor function. I wasn't sure if I could multiply through that or not and say n^2/2. Since it seems that you can, 1/2 is clearly scaling the order of the algorithm, which is n^2
     
  5. Nov 15, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure. floor(i/2) isn't exactly i/2 but it's pretty close. On the other hand n*log(n) is clearly way off.
     
  6. Nov 15, 2012 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Thinking about this a little more, isn't the more accurate estimate (1/4)*n^2? You don't just multiply but it's still basically n^2.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Algorithm Analysis (Big Theta)
  1. Big O analysis (Replies: 1)

Loading...