3 ms·

Great article. I've understood the why and what of Big-O but never how to do the analysis. I have a question for the informed however: The article says that w

Great article. I've understood the why and what of Big-O but never how to do the analysis. I have a question for the informed however: The article says that we only consider the fastest growing parts of an algorithm. So, counting instructions, n^2 + 2n would just be n^2. But why do we do that? Imagine an algorithm where we have n^12 + n^2 + n^2 + n^2 + n^2, etc. Do we really ignore each n^2 section? [Edited]

Qworg 14y ago
I assume you mean n^2 + 2n right? Given your example, you ignore the n^2 because n^12 grows SO much faster. For any "normal" amount of operations, n^12 wipes out 4*n^2 in terms of cost.
- mbenjaminsmith 14y ago
  Correct, I meant n^2. Certainly there are cases where the "insignificant" parts of an algorithm are not so, correct? In a simple case n^12 dominates a few n^2 sections, but there must be exceptions to that. Are there cases where a more complete analysis is done -- like comparing two similar algorithms? Or at that point are you actually implementing the algorithms to test and measure?
  - leif 14y ago
    In terms of just the expression, yes, you just count the largest term. In cases where you count more closely, it's either in the constant (quicksort vs mergesort) or in terms of removing randomness or amortization.
  - kruk 14y ago
    Yes, there are cases where the "insignificant" part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling. While the "insignificant" part would usually have to be really large to influence the running time, it's often the case that one algorithm is faster than another due to the second one having a large constant multiplier, even though the Big O notation would suggest otherwise (e.g. O(10nlogn) would be faster than O(1000*n)) It's also common that even if one of the algorithms is slower in the worst case scenario, its average case performance is better than asymptotically better solutions. A popular example of such might be the quicksort algorithm, which has the worst-case running time O(n^2) but in practice is usually faster than most O(nlogn) sorting algorithms.
    - malkia 14y ago
      for example binary search in array of strings woulde be overkill and performance hog, if the list on average has dozen elements (for example table with methods or commands)
    - mbenjaminsmith 14y ago
      "Yes, there are cases where the 'insignificant' part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling." I do understand that. My point was that the analysis is likely too optimistic in some cases. Maybe that's not an issue. I guess the whole thing is fairly arbitrary anyway, and conservative, since we're going to use "worst case" wherever it can be applied.
      - jkbyc 14y ago
        It is just a simple kind of analysis. Normally people working on algorithm and data structure analysis would do large amounts of fairly advanced math to analyse the complexity in detail, including all the "insignificant" parts. Apart from worst-case complexity, they would also analyse average complexity, amortized complexity, etc.
      - flebron 14y ago
        It's not about optimisim, but about eventual dominance of functions. If you have n^7 and 5(n^6 + 7n^2), then for every n >= 6, the first is larger. In general, for every pair of polynomials f and g of max degrees s and t respectively, and f will eventually dominate g if and only if s > t. Constant multiples are taken into account in big-O, but in a sense they can only delay the inevitable - for any nonzero constant multiples you pick to multiply f and g by, there always will exist a point n such that after that point, f dominates g forever. It might be that that n, however, is too large for your purposes - perhaps that's what you mean by optimism. Sedgewick has written about other types of analysis that take this into account, see Algorithms for the Masses: http://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf http://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf .
      - scott_s 14y ago
  - lotharbot 14y ago
    logs and fractional exponents often require deeper analysis. If n=1,000,000 then log n = 6, so n log n would actually be faster than 7n on that size data set. Certain special cases also require further analysis. Some algorithms run extremely fast, or extremely slow, on specific types of data. For example, with data that's expected to be nearly sorted, some sorting algorithms will run faster than expected while others can choke. Operations that run at very different speeds also require deeper analysis (or testing). If an algorithm requires O(n) disk reads, O(n^2) memory allocation, and O(n^4) calculations, it's possible for any one of those factors to dominate on real-life data sets.

Qworg 14y ago

I assume you mean n^2 + 2n right? Given your example, you ignore the n^2 because n^12 grows SO much faster. For any "normal" amount of operations, n^12 wipes out 4*n^2 in terms of cost.

mbenjaminsmith 14y ago
Correct, I meant n^2. Certainly there are cases where the "insignificant" parts of an algorithm are not so, correct? In a simple case n^12 dominates a few n^2 sections, but there must be exceptions to that. Are there cases where a more complete analysis is done -- like comparing two similar algorithms? Or at that point are you actually implementing the algorithms to test and measure?
- leif 14y ago
  In terms of just the expression, yes, you just count the largest term. In cases where you count more closely, it's either in the constant (quicksort vs mergesort) or in terms of removing randomness or amortization.
- kruk 14y ago
  Yes, there are cases where the "insignificant" part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling. While the "insignificant" part would usually have to be really large to influence the running time, it's often the case that one algorithm is faster than another due to the second one having a large constant multiplier, even though the Big O notation would suggest otherwise (e.g. O(10nlogn) would be faster than O(1000*n)) It's also common that even if one of the algorithms is slower in the worst case scenario, its average case performance is better than asymptotically better solutions. A popular example of such might be the quicksort algorithm, which has the worst-case running time O(n^2) but in practice is usually faster than most O(nlogn) sorting algorithms.
  - malkia 14y ago
    for example binary search in array of strings woulde be overkill and performance hog, if the list on average has dozen elements (for example table with methods or commands)
  - mbenjaminsmith 14y ago
    "Yes, there are cases where the 'insignificant' part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling." I do understand that. My point was that the analysis is likely too optimistic in some cases. Maybe that's not an issue. I guess the whole thing is fairly arbitrary anyway, and conservative, since we're going to use "worst case" wherever it can be applied.
    - jkbyc 14y ago
      It is just a simple kind of analysis. Normally people working on algorithm and data structure analysis would do large amounts of fairly advanced math to analyse the complexity in detail, including all the "insignificant" parts. Apart from worst-case complexity, they would also analyse average complexity, amortized complexity, etc.
    - flebron 14y ago
      It's not about optimisim, but about eventual dominance of functions. If you have n^7 and 5(n^6 + 7n^2), then for every n >= 6, the first is larger. In general, for every pair of polynomials f and g of max degrees s and t respectively, and f will eventually dominate g if and only if s > t. Constant multiples are taken into account in big-O, but in a sense they can only delay the inevitable - for any nonzero constant multiples you pick to multiply f and g by, there always will exist a point n such that after that point, f dominates g forever. It might be that that n, however, is too large for your purposes - perhaps that's what you mean by optimism. Sedgewick has written about other types of analysis that take this into account, see Algorithms for the Masses: http://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf http://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf .
    - scott_s 14y ago
- lotharbot 14y ago
  logs and fractional exponents often require deeper analysis. If n=1,000,000 then log n = 6, so n log n would actually be faster than 7n on that size data set. Certain special cases also require further analysis. Some algorithms run extremely fast, or extremely slow, on specific types of data. For example, with data that's expected to be nearly sorted, some sorting algorithms will run faster than expected while others can choke. Operations that run at very different speeds also require deeper analysis (or testing). If an algorithm requires O(n) disk reads, O(n^2) memory allocation, and O(n^4) calculations, it's possible for any one of those factors to dominate on real-life data sets.