[RESOLVED] Big-Oh Notation Question
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Thread: [RESOLVED] Big-Oh Notation Question

Hybrid View

  1. #1
    Join Date
    Oct 2012
    Posts
    9

    [RESOLVED] Big-Oh Notation Question

    Ive been trying to figure out what the big-O notation is for this code segment:

    for (int count =1; count < n; count++)
    {
    int count2 = 1;

    while (count2 < count)
    {
    count2 = count2 * 2;
    }
    }

    My friend has been telling me its O(N^2) but I dont know if that is correct and if it is correct, I have no clue how they found that answer.

    Anyone have any ideas???

  2. #2
    Join Date
    Oct 2008
    Posts
    1,120

    Re: Big-Oh Notation Question

    your friend is wrong, it's not O(n^2). Try counting the number of cycles in the inner loop given an arbitrary "count" value; then, sum the result from 1 to n; you'll get ...

  3. #3
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    Looks to me like the inner loop wont run for the first time through the segment because count2 is equal to count. After count is incremented once that inner loop will have to run one more time every time through. So it cant just be O(n) right?
    Last edited by quixomatic; October 20th, 2012 at 12:58 PM.

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,266

    Re: Big-Oh Notation Question

    Quote Originally Posted by quixomatic
    After count is incremented once that inner loop will have to run one more time every time through.
    Not quite: notice that count2 is doubled, not incremented, on each iteration of the inner loop. As such, what is the complexity of the inner loop?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    The complexity of the inner loop is O(2^n) then? Each time it multiplies count2 by 2 ...this stuff is driving me crazy I just cant wrap my head around it.

    Then the complexity of the outer loop would just be O(n)?

    Do you add the two big-o notations of the loops?

  6. #6
    Join Date
    Oct 2008
    Posts
    1,120

    Re: Big-Oh Notation Question

    for now, forget the big-oh and just answer this question: given an integer n, how many times the line "count2 = count2 * 2" is invoked ?

  7. #7
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    the while loop would get invoked n-1 times

  8. #8
    Join Date
    Oct 2008
    Posts
    1,120

    Re: Big-Oh Notation Question

    not the while loop, I said: how many times the line "count2 = count2 * 2" is invoked ?

  9. #9
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    Just once per while loop

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,266

    Re: Big-Oh Notation Question

    Quote Originally Posted by quixomatic
    Just once per while loop
    If that were true, then this C++ program:
    Code:
    #include <iostream>
    
    int main()
    {
        int n = 5;
        for (int count = 1; count < n; count++)
        {
            int count2 = 1;
            while (count2 < count)
            {
                count2 = count2 * 2;
                std::cout << count2 << ' ';
            }
        }
        std::cout << std::endl;
    }
    would have the exact same output as this C++ program:
    Code:
    #include <iostream>
    
    int main()
    {
        int n = 5;
        for (int count = 1; count < n; count++)
        {
            int count2 = 1;
            if (count2 < count)
            {
                count2 = count2 * 2;
                std::cout << count2 << ' ';
            }
        }
        std::cout << std::endl;
    }
    However, the former gives me the output:
    Code:
    2 2 4 2 4
    and the latter gives me the output:
    Code:
    2 2 2
    Clearly, your statement must be wrong.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    Quote Originally Posted by laserlight View Post
    If that were true
    ...
    Clearly, your statement must be wrong.
    Appreciate the help but I figured it out just looking at the patterns of the code and determined the outer loop is O(N) and that the inner loop just performs 2^n like I said earlier, which in log base 2 is just logN.

    Since the while loop is inside of outer loop I multiplied O(N) by O(logN) giving me O(NlogN)

  12. #12
    Join Date
    Oct 2008
    Posts
    1,120

    Re: Big-Oh Notation Question

    sorry, it's still wrong. Again, count the number of times the inner loop cycles ( no, it's not 1 nor 2^n. try following the code as it runs, eventually with a debugger or just with pen and paper ).

  13. #13
    Join Date
    Oct 2012
    Posts
    9

    Re: Big-Oh Notation Question

    Quote Originally Posted by superbonzo View Post
    sorry, it's still wrong. Again, count the number of times the inner loop cycles ( no, it's not 1 nor 2^n. try following the code as it runs, eventually with a debugger or just with pen and paper ).
    You know what, I really dont care...I worked on this for a huge chunk of yesterday and it was only a tiny fraction of my assignment. Not only that I was trying to be nice saying I appreciate the help, but what help have you given? Day and a half later and still not even a single post on what direction I should take other than "how many times was count = count * 2 invoked. I've asked multiple people who know how to find big-oh and they all agree its nlogn.

  14. #14
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,266

    Re: [RESOLVED] Big-Oh Notation Question

    Quote Originally Posted by quixomatic
    the inner loop just performs 2^n like I said earlier, which in log base 2 is just logN.
    You did not say that. Rather, you asked if "the complexity of the inner loop is O(2^n)". It isn't, as you yourself have now concluded. What you probably have in mind is the idea that the value of count2 increases at a rate proportional to 2^n. Thus, the number of iterations of the inner loop is proportional to log n.

    Quote Originally Posted by quixomatic
    Since the while loop is inside of outer loop I multiplied O(N) by O(logN) giving me O(NlogN)
    Yes, that is correct

    EDIT:
    Quote Originally Posted by quixomatic
    Day and a half later and still not even a single post on what direction I should take other than "how many times was count = count * 2 invoked.
    The thing is, figuring that out is the key to figuring out the complexity of the inner loop, and is likely to be the core lesson of this exercise. Once you know the complexity of the inner loop, the overall complexity of the code snippet is obvious since the outer loop's complexity is obvious.
    Last edited by laserlight; October 21st, 2012 at 12:03 PM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  15. #15
    Join Date
    Oct 2012
    Posts
    9

    Re: [RESOLVED] Big-Oh Notation Question

    Appreciate the response Laserlight, I admit I did not have an strong understanding of what complexity is or how to find it, but when I said it performs 2^n I did mean that the inner function itself was computing exactly that. I may have reached my answer differently, but never once did superbonzo say I was getting closer or that I had the right idea.

Page 1 of 2 12 LastLast

Tags for this Thread

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center