Coffeehouse Post

Single Post Permalink

View Thread: The BigO notation.
  • User profile image

    AndyC said:
    kriskdf said:

    Big O is great in 'theoretical' terms, but in practical terms 'N' is always bounded and as such Big O isn't necessarily a good indicator for real world comparisons of two algorithms/data structures since the effect of constants dropped from a big O calculation can be very significant. Practical things like page faults and the non-linear speed of memory addressing (due to layers of caching) can be, and generally are, far more significant in determining how something scales within realistic bounds.

    well...i guess if you make N a constant by giving it a practical bound you can decide which contant has the biggest impact on overall performance. Smiley  I work on Bing and N can be very big and continues to grow.  Because N is so big, the BigO is important, as is the constant.  Spending 1 second on a web doc has huge impact compared to 500ms.  Going from O(N) to O(NlogN) is huge if N is bounded at 100B or so.  How much would you need to reduce the constant time to make it worth sticking with O(NlogN) over O(N)?  How about at a trillion docs?


    So i guess the conclusion is that BigO and the constant are important depending on the situation. Smiley