Average case complexity

This is a discussion on Average case complexity within the C++ Programming forums, part of the General Programming Boards category; Looks like this question has been asked before, but I am not able to find an answer to it so ...

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    20

    Average case complexity

    Looks like this question has been asked before, but I am not able to find an answer to it so I will ask again.

    How do you compute the complexity of an algorithm in an average case? I can (barely) understand why Quicksort has O(n^2) in worst case, but I cannot figure out why it has O(nlogn) in an average case. Thanks so much.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    I'll take a stab and say that it has to do with the fact that the sum of the number of items from the smaller half of each partition step follows the normal distribution. (Assuming say a random splitter choosing technique)

    At one end of the bell curve lies the chance of hitting the worst possible case with zero items in the smaller half every time. At the other end of the bell curve we have the case where the halves are equal every time.

    Somewhere near the middle of the bell curve you get approximately a 1/3rd 2/3rd split on average, and the most likely cases are around there. That case is O(n * log n)

    Does that make sense to you?
    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"

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    20
    Thanks a lot iMalc. I manage to understand until where you mention the most likely cases are around the 1/3rd 2/3rd split on average, which I also understand, but how does one compute that that case is O(nlogn)? If this is derived according to some Math theories than I will have to dig up my university text books. Cheers.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    I'll assume you can see how the perfect case of equal items on each side every time is O(n * log n). If not, let me know.

    The maximum recursion depth for such a case is ceil(log base 2 of n). I.e. Log base 2 of 1000 is 9.9657 which we round up to 10.
    Now if you get about a 1/3rd 2/3rd split then the maximum recursion depth should be within a constant factor of the perfect case. I can't think of an easy way to show why that is at the moment. In that case the constant factor might be about 2, meaning that the expected maximum recursion depth might be around 20.
    In Big-Oh notation we simply ignore that constant factor.

    Note that I'm not even sure that a 1/3rd 2/3rd split is exactly the average case, but that is not important. For all I know the actual average case might involve the golden ratio or whatever..., but basically the average case will involve only a constant factor times the maximum recursion depth of the perfect case.
    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"

  5. #5
    Registered User
    Join Date
    Feb 2006
    Posts
    20
    Thanks again for the explanations iMalc. This is complicated, but I think I understand now. Cheers!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How can I make this code more elegant?
    By ejohns85 in forum C++ Programming
    Replies: 3
    Last Post: 04-02-2009, 08:55 AM
  2. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  3. Can someone please clean up my code
    By ki113r in forum C Programming
    Replies: 10
    Last Post: 09-12-2007, 10:03 AM
  4. Reducing Code size from ridiculous length
    By DanFraser in forum C# Programming
    Replies: 10
    Last Post: 01-18-2005, 04:50 PM
  5. Keypress reading
    By geek@02 in forum Windows Programming
    Replies: 1
    Last Post: 06-16-2004, 12:16 PM

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