Results 1 to 19 of 19

Thread: Big O notation

  1. #1
    simorgh is offline Member
    Join Date
    Jan 2010
    Posts
    25
    Rep Power
    0

    Default Big O notation

    May some one explain about Big O notation?

    Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Quote Originally Posted by simorgh View Post
    May some one explain about Big O notation?
    Rather than ask someone to repeat a chapter and verse that's already been written, you are probable much better off reading the Wikipedia article (or the many articles found on Google), and then ask specific questions on what it is you don't understand in the articles. That way you'll save folks from typing out pages of info that you already know, and that way we have a much greater chance of being able to help you.


    Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?
    Not that I know of, but Google again knows much more than me in this regard.

    Edit: although I'm not sure how software can do this -- analyze algorithms of code written in Java -- or if it's even possible.

    Much luck!
    Last edited by Fubarable; 05-01-2010 at 12:38 PM.

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

    Default

    Quote Originally Posted by Fubarable View Post
    Edit: although I'm not sure how software can do this -- analyze algorithms of code written in Java -- or if it's even possible.
    It can't be done; embed two differnt big-Oh algoritms in a decision that involves an undecidable problem:

    Java Code:
    if (PostCorrespondenceProblem(pcp)) // is pcp solvable?
       // do something, say, O(n^2)
    else
       // do something else, say, O(2^n)
    To be able to answer this big-Oh question the analyzer has to be able to solve any instance of a pcp and it can't do that.

    kind regards,

    Jos

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Quote Originally Posted by JosAH View Post
    It can't be done; ....
    Thanks for elucidating this!

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

    Default

    Quote Originally Posted by Fubarable View Post
    Thanks for elucidating this!
    No problem, you're welcome; those undecidable problems are my favourites; they save (lazy) math folks a lot of tedious proving: simply reduce another problem to one of those and you're ready, no more discussion about it ;-)

    kind regards,

    Jos

  6. #6
    developersh is offline Member
    Join Date
    May 2010
    Posts
    1
    Rep Power
    0

    Default

    Quote Originally Posted by simorgh View Post
    May some one explain about Big O notation?

    Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?
    Actually Big o notation shows that complexity of your code in a program & the it will be upper limit of your complexity means that how much time will be exceed to execute the code Big O notation describe as O(n) < O(log n) < O(n*n)<O(n*n*n) like wise

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

    Default

    Quote Originally Posted by developersh View Post
    Actually Big o notation shows that complexity of your code in a program & the it will be upper limit of your complexity means that how much time will be exceed to execute the code Big O notation describe as O(n) < O(log n) < O(n*n)<O(n*n*n) like wise
    O(n) < O(log n)? I don't think that can be true.

    kind regards,

    Jos

  8. #8
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Big-O notation means this:

    f(n) = O(g(n)) iff exist integers N, C such that for all x > N, f(x) < C*g(x)

    N means "the condition will work for all large integers after N". For example, consider these functions:
    f(x)=10*x
    g(x)=x^2

    which one is larger?

    makes sense that g(x) is larger, but if you take x=5, it doesn't hold. N in the formula above means you can ignore all small x, so you can say this: g(x)>f(x) for all x>100, and thus, f(x) is O(g(x)).

    now consider these two functions:

    f(x)=x^2+10
    g(x)=x^2

    makes sense they should be equally large: when x grows, the +10 will not really matter. for that, in definition above they introduce constant C. So you can say this: for all x>100, since f(x)<2*g(x), and thus, f(x) is O(g(x)).

    In practice:

    if you have a polynom, it's O(x^highest power). so 3*x^2+21x+48 is O(x^2)

    x < log x < sqrt x < x < x logx < x^2 < x^2 log x < x^3 ... < 2^x

    2^x = e^x = 3^x = anything^x < x^x

    n! is its own thing...


    hope that helps

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

    Default

    Quote Originally Posted by iluxa View Post
    n! is its own thing...
    No it isn't, you can use Stirling's approximation.

    kind regards,

    Jos

  10. #10
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    sh-h-h! I'm trying to keep things relatively simple here!

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

    Default

    Quote Originally Posted by iluxa View Post
    sh-h-h! I'm trying to keep things relatively simple here!
    Sorry 'squire, it won't happen again, promised.

    kind regards,

    Jos

    ps. n! < n^n

  12. #12
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    can you prove that an array cannot be sorted in better than n log(n)?

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

    Default

    Quote Originally Posted by iluxa View Post
    can you prove that an array cannot be sorted in better than n log(n)?
    There's a nice proof in Donald Knuth's "The Art Of Computer Programming" vol III: "Searching and Sorting". I also found another (similar) proof here.

    kind regards,

    Jos

  14. #14
    simorgh is offline Member
    Join Date
    Jan 2010
    Posts
    25
    Rep Power
    0

    Default

    O(N) = as you increase the size of input, the time taken to complete operations scales linearly with that size
    Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
    When I check images in this site:

    An Intro to Big Oh Notation with Java NerdGerl

    I see they use big O in order to find the relationship between size on input and time.In fact, I think Big o is a function that represent If size of input being increased, How much time of running of algorithm will be increase. Is it right?

    But then there is another question, If it is about the size of input, Then size of for example a number, will be unlimited. then there is worst case after worst case.Then we can not say this is the worst case, because there is another worst case too.



    I really get confused!


    Another question:

    Java Code:
    k=0;
    for(i=0; i<n; i++)
    k++
    It is said the worst case here is : o(n)

    Now my question is:

    If it is the worst case, Then what can be the average case for this?
    &gt;

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

    Default

    Quote Originally Posted by simorgh View Post
    Another question:

    Java Code:
    k=0;
    for(i=0; i<n; i++)
    k++
    It is said the worst case here is : o(n)

    Now my question is:

    If it is the worst case, Then what can be the average case for this?
    &gt;
    That example doesn't show what your problem is about: its worst case is also its best case and its also its average case. Take this example: let int[] array be an unsorted array of length n. Searching for a number m takes n steps worst case, n/2 steps average case and 1 step in the best case. The worst case and average case are both O(n). The best case takes O(1) steps in the rare event that the first array element is the wanted element.

    kind regards,

    Jos

  16. #16
    simorgh is offline Member
    Join Date
    Jan 2010
    Posts
    25
    Rep Power
    0

    Default

    k=0;
    for(i=0; i&lt;n; i++)
    k++;
    k=0;
    for(j=0; j&gt;&lt;n; j++)
    k++;
    Sequential for loops are not related and loop independently of each other. The first loop will execute
    n times. The second loop will execute n times after the first loop finished executing. The worst case
    timing will be:
    O(n) + O(n) = 2 * O(n) = O(n)
    We drop the constant because constants represent 1 time unit. The worst case timing is O(n)
    .
    I read this in a tutorial.

    May you explain more about this:

    O(n) + O(n) = 2 * O(n) = O(n)

    Another question:

    Java Code:
    k=0;
    for(i=0;i&lt;n;i++)
    for(j=i;j&lt;n;j++)
    k++;
    In this situation we calculate the worst case timing using both loops. For every i loop and for start of
    the inner loop j will be n-1 , n-2, n-3…
    O(1) + O(2) + O(3) + O(4) + ......
    which is the binomial series:
    n ( n - 1) n^2 - n n^2
    ------------ = ----------- = ------ = O(n2)
    2 2 2

    May you explain more about this


    third question

    Java Code:
    k = 0;
    for(i=1; i&lt;=n; i=i*2)
    for(j=1; j&lt;=i; j++)
    k++;
    What is Big O for this code?

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

    Default

    Quote Originally Posted by simorgh View Post
    May you explain more about this: [ ... ]
    Another question: [ ... ]
    May you explain more about this [ ... ]
    third question [ ... ]
    Do you want fries on top of that?

    kind regards,

    Jos

    ps. do your own homework.

  18. #18
    simorgh is offline Member
    Join Date
    Jan 2010
    Posts
    25
    Rep Power
    0

    Default

    It is not the home work, Just a few questions

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

    Default

    Quote Originally Posted by simorgh View Post
    It is not the home work, Just a few questions
    Well, then show some effort; we are not a free answering service here.

    kind regards,

    Jos

Similar Threads

  1. Big O notation
    By vendetta in forum New To Java
    Replies: 6
    Last Post: 01-08-2010, 07:47 PM
  2. Big O notation question
    By kira137 in forum New To Java
    Replies: 4
    Last Post: 10-14-2009, 08:07 PM
  3. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 06:02 PM
  4. Postfix-Notation
    By little_polarbear in forum New To Java
    Replies: 9
    Last Post: 09-09-2008, 04:24 PM
  5. Big Oh Notation and Heaps
    By gibsonrocker800 in forum Advanced Java
    Replies: 8
    Last Post: 01-25-2008, 10:06 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
  •