Coffeehouse Thread

8 posts

Asymptotic Analisys

Back to Forum: Coffeehouse
  • User profile image
    Deactivated User

    Comment removed at user's request.

  • User profile image
    Deactivated User

    Comment removed at user's request.

  • User profile image
    amotif

    Shmuelpro wrote:
    oh common can anyone at least tell me that they know what it is


    I think we most often refer to "Big-O notation" in discussing the magnitude of algorithms... is that where you're going with this?

  • User profile image
    SvendTofte

    amotif wrote:
    Shmuelpro wrote: oh common can anyone at least tell me that they know what it is


    I think we most often refer to "Big-O notation" in discussing the magnitude of algorithms... is that where you're going with this?


    There's several versions of algoritihmic analysis. Big O is the most common, and often it's quite intuitive. IIRC, O is the maximum time/resource that will ever be spent. You have other symbols for things, like "minimum possible resource expenditure", and average. Average runtime analysis is hard, but needed.

    Quicksort is a O(n^2) algorithm. Like Bubble sort. That is, the runtime of the algorithm is proportional to the square of the length of the input (the number of items to be sorted).

    If you do propability analysis on the formular however, you will find the run time to near O(n log n), which is a theoretical lower bound for comparison based sorted (bucket sort is in theory faste, as it does not compare, in order to sort). QS will only ever hit the worst time, when it's splitting the array to be sorted, when selection of the pivot point results in a constant split, such as:

    [2 elem] [pivot elem] [rest of elem]

    However, bad luck like this is extremely unlikely, and as long as you're getting splits, like this:

    [x % of elems] [pivot elem] [rest of elem]

    Then the time it takes, will be O(n log n).

    I don't know what Wikipedia says on the topic, but the page on QS is awefully long: http://en.wikipedia.org/wiki/Quicksort

    A pretty standard book on the analysis of algorithms and datastructures is the "Introduction to Algorithms" from MIT Press, by Cormen, et al.

  • User profile image
    Deactivated User

    Comment removed at user's request.

  • User profile image
    amotif

    SvendTofte wrote:

    I don't know what Wikipedia says on the topic...


    Wikipedia: Big O notation

  • User profile image
    BruceMorgan

    In my experience at Microsoft, it's relatively common to do perf analysis this way.  Certainly we talk about "n squared" vs "n log n" vs "linear" algorithms quite frequently.

    In interviews, I often expect candidates to be able to intelligently discuss the performance characteristics of the algorithm they're using.  More often than not, this means talking in "Big-O" notation.

  • User profile image
    kriskdf

    Yeah,  I've never done any recurance equations or actual math to figure it out.  I must say that after several advanced algorithms classes where you have to do that stuff over and over again you get to the point where you can look at code and you just know it's runtime characteristics.

    That being said, during interviews I ask questions that have multiple possible answers, each having different runtime characteristics.  The inteviewee must be able to select the best one and choose why (often the best solution depends on context).

    I have had to do the math a few time to select which algorithm/approach would be best for certain conditions (which will perform best with 100,000 sorted items vs 100 unsorted items?).  When you work on a performance critical system you have to be able to defend your choices in algorithms and data structures.

    It is important stuff to learn and anyone who is serious about getting into software development should learn algorithm analysis.

Comments closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.