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!

Help finding Complexity in Big-O notation

  1. Jan 25, 2013 #1
    1. The problem statement, all variables and given/known data

    I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or proved that it's bounded by [tex] n^3 [/tex]or [tex] n^4 [/tex] ? Thank you!

    2. Relevant equations

    [tex] \sum_{j=3}^{n} \left[(j-1)[2(j-2)-1] + \sum_{i=2}^{j-2}(i) +
    \sum_{k=2}^{j-2}\left[k(j-(k+1))+\sum_{i=k}^{j-2}(i)\right]\right] [/tex]

    3. The attempt at a solution

    I run 1000 numbers and apparently it is bounded by [tex] n^3 [/tex].
     
    Last edited by a moderator: Jan 25, 2013
  2. jcsd
  3. Jan 25, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    First simplification step:
    [tex] \sum_{j=3}^{n} \left[O(n)O(n) + O(n^2) +
    \sum_{k=2}^{j-2}\left[k(j-(k+1))+\sum_{i=k}^{j-2}(i)\right]\right] [/tex]
    To get O(n^3) I think you have to evaluate the innermost sum to cancel some parts of the k(j-(k+1)), but apart from that (or for an O(n^4)-boundary) you can always estimate those terms as bounded by n, with rules like O(n)O(n)=O(n^2) and so on.
     
  4. Jan 25, 2013 #3
    I see.
    To be honest I would like to get a [tex] n^3 [/tex] :-), but I see what you are saying.
    I have plotted it against [tex] n^3 [/tex] for [tex] n [/tex] from 1 to 10,000 and I guess I got carried away because it seemed to be asymptotically bounded, but of course, there's no guarantee, at all.
    I will try to open the sum and see if it cancels out, as you suggested, if not, I'll consider [tex] n^4 [/tex].
    Thank you so much!
     
  5. Jan 25, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't think this is O(n^3).
    I would expect O(n^4), and this is easy to show.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help finding Complexity in Big-O notation
  1. Big O Notation Proofs (Replies: 0)

  2. Finding the Big-O! (Replies: 1)

Loading...