3 ms·
Big O is literally easier than the analytical alternative. I didn't "understand" Big-O until I read Donald Knuth's "Art of Computer Programming". I forget exac
by dragontamer 6y ago
Big O is literally easier than the analytical alternative.
I didn't "understand" Big-O until I read Donald Knuth's "Art of Computer Programming". I forget exactly where Knuth does this... but Knuth derives the _exact_ number of average runtime on some algorithm. (Where "average" is defined as all possible permutations of the input).
I forget why or where this derivation was, but it was along the lines of 3nlog(n) + 5n +25, or something along those lines (I made up the numbers).
Solving for the specific and exact runtime of a function is very, very, very difficult. Instead of doing that, Comp. Sci has decided that the easier Big-O is "good enough" for most purposes.
That's it. Big-O is ALWAYS easier to calculate than the exact runtime. Yeah, its still hard in some cases, and there are situations like Radix sort (O(n)) vs Quicksort (O(n*log(n)), or Karatsuba multiplication vs optimal multiplication (like O(n^1.5) vs O(n^1.4...)) where the "slower Big-O" is better in practice.
But such situations are rare, and are easily figured out through profiling.
---------
So lets do some real-talk. Most programmers don't wait on their code anymore. Computers are so fast, that all this algorithmic complexity is a red herring compared to other issues. By and large, inefficient programming languages are being used in grossly inefficient ways and no one cares.
For most practical purposes, profiling with a stopwatch is your go-to methodology for analyzing algorithms. If that's not good enough, then profiling with a dedicated profiler (which can statistically count specific situations: like cache-hits or branch-mispredictions, as well as how many times any particular line of code ran).
That's the information you want and need. Take the runtimes, plot it on a log-log plot, fit a growth-exponent on the curve and BAM, you got O(n^whatever).
Where Big-O comes in are the situations where you're waiting for your code to finish. You run your code, and you wait 10-minutes, 1-hour, 10-hours, 2-days... will your code finish? Do you have an infinite loop? Or is it actually making forward progress? If so, how long do you estimate it to last? (And indeed: Hollywood movies are known to take multiple days to render a single frame, so these situations come up every now an then in practice).
Under such a situation, you can't really run a profiler or use a stopwatch. You probably can run a big-O analysis by pen-and-paper over your code however, and then get an estimate on the size of your data. You'll want to make sure that you're O(n) or O(n*log(n)). If you're getting O(n^2) or O(n^3) from an algorithm that's taking days to run... you might be in trouble.