Results 1 to 4 of 4
  1. #1
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    264
    Rep Power
    2

    Default Big Oh of a method

    Java Code:
    for ( int i=0; i < n; i++ ) { 
     for ( int j=0; j < n*n; j++ ) { 
     for ( int k=0; k < j*j; k++ ) { 
     a[k] = a[k] + sum; 
     } 
     } 
    }
    is this method O(n^7) ?

    I think so, because it's n*n^2*n^2*n^2, can someone verify my answer?

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: Big Oh of a method

    Oops, you got me there: the loops run in O(n), O(n^2) and O((n^2)^2) times (from outer to inner loop); so the total runtime is O(n^7)

    kind regards,

    Jos
    Last edited by JosAH; 12-20-2013 at 09:07 PM.
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,544
    Rep Power
    5

    Default Re: Big Oh of a method

    It appears so. But there may be a more accurate O notation to describe it.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: Big Oh of a method

    Quote Originally Posted by jim829 View Post
    It appears so. But there may be a more accurate O notation to describe it.
    That is called 'big-T' notation T(n), see Knuth, he loves that ;-) As far as big-Oh notation is concerned, n database accesses and n increments are both O(n)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 1
    Last Post: 12-12-2013, 07:08 PM
  2. Replies: 7
    Last Post: 04-11-2013, 05:31 AM
  3. Replies: 2
    Last Post: 03-23-2012, 04:53 AM
  4. Replies: 1
    Last Post: 10-17-2011, 01:00 AM
  5. Replies: 29
    Last Post: 09-25-2008, 07:55 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •