New answers tagged

2

You might measure that a particular implementation of an algorithm on a particular computer takes say $315 n^2$ nanoseconds, plus/minus 10%. And an implementation of a different algorithm on the same computer is measured to take $409 n^2$ nanoseconds, plus/minus 6%. I guess you will prefer the first algorithm. Big-O notation and asymptotic complexity ignores ...


3

Asymptotic notation is not fine-grained enough capture the difference between $n$ and $2n$ operations, and there are good theoretical reasons not to care about multiplicative constants unless we want to specify the nitty-gritty details of the model of computation at hand and of our algorithms. That said, you could say that both algorithms require $\Theta(n)$ ...


Top 50 recent answers are included