Like Tree2Likes

Is this the correct big O average case complexity for this algorithm?

This is a discussion on Is this the correct big O average case complexity for this algorithm? within the C++ Programming forums, part of the General Programming Boards category; Code: unsigned rnd(unsigned limit) { return rand() % limit; // O(1) } void permute (int a[], int n) { bool* ...

  1. #1
    Registered User
    Join Date
    Jul 2013
    Posts
    3

    Is this the correct big O average case complexity for this algorithm?

    Code:
    unsigned rnd(unsigned limit)
    {
        return rand() % limit;           // O(1)
    }
     
    void permute (int a[], int n)
    {
        bool* used = new bool[n];        // O(1)
        fill (used, used+n, false);      // O(used+n)
        for (int i = 0; i < n; i++)      // O(1)  n*  = O(n)
        {
            a[i] = rnd(n);               // O(1)
            while (used[a[i]])           // O(1)  n* = O(n)
            {
                a[i] = rnd(n);           // O(1)
            }
            used[a[i]] = true;           // O(1)
        }  
        delete [] used;                  // O(1)
    }
    So it would be O(used+n3)?
    Last edited by blackvelvet; 07-14-2013 at 05:03 PM.

  2. #2
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    The for loop and while loop both run in linear time (O(n)) and since they are nested you would get quadratic complexity (O(n^2)). The fill operation is not in any loop however so i don't know why you end up with O(n^3), it should be O(n + n^2)....however:

    Coefficients and constant factors are usually omitted from complexity analysis since they are practically irrelevant for large values of n. Therefore i would say the correct answer is O(n^2).

    Edit:

    Having looked at the code a bit harder, i'm having doubts about that inner while loop being O(n). The amount of iterations is basically random, i'm not quite sure how that is expressed in big-O. I mean if the PRNG is particularly bad it could be stuck in a cycle and never terminate, and on those grounds i would say this doesn't qualify as a correct algorithm, since an algorithm has to terminate at some point. Someone tell me why i am wrong?
    Last edited by Neo1; 07-14-2013 at 07:14 PM.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    That doesn't even make sense. used is a pointer!?

    The inner loop is a little tricky, since it has a "random" factor in how many times it repeats.

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,451
    Quote Originally Posted by oogabooga View Post
    The inner loop is a little tricky, since it has a "random" factor in how many times it repeats.
    What's so tricky about it? We have an even distribution. Average value will be n/2. Complexity of the loop O(n)
    iMalc likes this.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    The number of iterations of the inner loop follows the binomial selection with replacement probabilities.
    E.g. 4 items.
    First time through outer loop, we have 0% chance of entering the inner loop.

    Second time through the outer loop, we have a 25% chance of entering the inner loop, and for subsequent iterations. The chance of exactly N iterations is:
    (0.25^N * 0.75)*100
    E.g.
    75% chance of requring no inner loop iterations.
    18.75% chance of requiring one inner loop iteration.
    4.6875% chance of two iterations.
    You can see that the chance of iterating again diminishes very rapidly.

    Third time through the loop, we are half-filled and the chance of exactly N iterations is:
    (0.5^N * 0.5)*100
    E.g.
    50% chance of requring no inner loop iterations.
    12.5% chance of requiring one inner loop iteration.
    6.25% chance of two iterations.

    Last time through the loop, the chance of exactly N iterations is:
    (0.75^N * 0.25)*100
    E.g.
    25% chance of requring no inner loop iterations.
    18.75% chance of requiring one inner loop iteration.
    14.0625% chance of two iterations.

    At half-full, you can see that the average number of iterations is still only about one half. It does get high as the end nears. For the last item I think it's fairly clear than it will require on average N/2 iterations to find the hole, but even the one before that will only require about N/4 iterations, so it's not that bad.

    The exact math to prove it escapes me right now, but I believe that the correct answer is that it's actually O(n) average case overall for the whole function.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,145
    O_o

    This strikes me as being "O(3n)" which is just "O(n)". (The `fill' and the `for' each being "O(n)" while on average the`while' only approaches "O(n)".)

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The outer loop repeats n times.
    The inner loop repeats, on average, n/2 times for every iteration of the outer loop.
    n * (n/2) = (n*n)/2
    So isn't it O(n*n)?

  8. #8
    Registered User
    Join Date
    Jul 2013
    Posts
    3
    So it should be like this...?

    Code:
    unsigned rnd(unsigned limit)         
    {
        return rand() % limit;           // O(1)
    }
    
    void permute (int a[], int n)
    {
        bool* used = new bool[n];        // O(1)
        fill (used, used+n, false);      // O(n+n^2)
        for (int i = 0; i < n; i++)      // O(1)  n*  = O(n)
        {
            a[i] = rnd(n);               // O(1)
            while (used[a[i]])           // O(1)  n*  = O(n)       
            {
                a[i] = rnd(n);           // O(1)
            }
            used[a[i]] = true;           // O(1)
        }  
        delete [] used;                  // O(1)
    }
    And the average case complexity would be O(n^2)?

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,411
    fill is presumably linear complexity, judging from its name.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,145
    The `fill' and the `for' each being "O(n)" while on average the`while' only approaches "O(n)".
    *derp*

    Well, that would actually be "O(n * log n)".

    *shrug*

    Drunk at the wheel...

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  11. #11
    Registered User
    Join Date
    Jul 2013
    Posts
    3
    I'm confused It seems like everyone is giving a different answer

  12. #12
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by phantomotap View Post
    *derp*

    Well, that would actually be "O(n * log n)".

    *shrug*

    Drunk at the wheel...

    Soma
    I could see why this would be the case if the inner loop was O(log n), but according to iMalcs rather detailed reply earlier in this thread it seems it is actually O(n) thus making the total O(n^2), where is this O(n log n) coming from?
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,145
    I could see why this would be the case if the inner loop was O(log n), but according to iMalcs rather detailed reply earlier in this thread it seems it is actually O(n) thus making the total O(n^2), where is this O(n log n) coming from?
    O_o

    My statement may be right or wrong, but it has nothing to do with what iMalc posted.

    I was simply correcting a flaw in my own statement; with my logic, the inner loop essentially misses according to the binary logarithm of the filled slots scaled by a, nearly, constant factor. (The constant factor would be ignored with "Big O".) I had removed the entire scaling factor in my original thoughts ("O(n)") instead of just the constant ("O(n * log n)").

    Also, you misunderstood what iMalc posted; if what iMalc shows is entirely accurate, that would make the entire process, a call to `permute', "O(n)" not "O(n^2)".

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,017
    Best case: O(n) (inner loop never gets executed)

    Worst case:
    EDIT:Worst case is that it never terminates.

    Because the worst case is worse than the best case, the average is surely more than O(n), but maybe by a small power >1 of N.
    Last edited by King Mir; 07-15-2013 at 09:23 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by King Mir View Post
    Best case: O(n) (inner loop never gets executed)

    Worst case:
    EDIT:Worst case is that it never terminates.

    Because the worst case is worse than the best case, the average is surely more than O(n), but maybe by a small power >1 of N.
    It is entirely possible for the expected or average case to match the best case. Particularly when the best base might be N operations and the average case might be 3N operations. Both are still O(n).

    When you assume an even distribution, this problem turns into one of probabilities where each outcome is equally likely.
    Let me state it more clearly: The whole thing is indeed O(n)
    Those that arrived at the O(n*n) assumption have missed the fact that even when the boolean array is half filled, you still have a 50/50 chance of of hitting a false entry on your first random number. So when half filled you can expect an average case of half an extra iteration. Clearly it is nowhere near n/2 iterations on average, it only gets that bad for the very last item!

    It's probably the same proof as the proof that escaped mathematicians for years where if you move half a metre in half a second, then a quarter of a meter in a quarter of a second, then an eighth of a meter in an eighth of a second etc etc, prove you actually end up reaching the 1 metre mark. The sum to infinity suggests that you don't, but in reality it is obvious that you are travelling at a constant speed. Along the same lines of whatever proof was eventually discovered for that, the inner loop here is amortised constant time.

    Yes if the random number generator is extremely poor then it is possible for this to never terminate, but it would have to be so poor that certain numbers could never be generated at all, which is incomprehensibly non-random, and in all likelihood would not meet the C standard.
    Last edited by iMalc; 07-16-2013 at 04:18 AM.
    stahta01 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Time complexity of algorithm
    By viblic in forum C Programming
    Replies: 2
    Last Post: 01-11-2012, 10:22 AM
  2. Average case complexity
    By alois_rone in forum C++ Programming
    Replies: 4
    Last Post: 12-23-2007, 06:56 PM
  3. Algorithm Complexity
    By logicwonder in forum C Programming
    Replies: 4
    Last Post: 01-09-2006, 05:03 AM
  4. Worst-case complexity of this function?
    By Ariod in forum C Programming
    Replies: 3
    Last Post: 08-17-2005, 02:17 PM
  5. Algorithm - Complexity.
    By visitant... in forum C Programming
    Replies: 5
    Last Post: 05-13-2003, 02:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21