As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
1 Answer
$\begingroup$
$\endgroup$
The most conspicuous use of big O notation is in the analysis of running times of algorithms. Since the exact running time depends on the cost of specific instructions, there is no point in saying that a certain algorithm takes time $14.3n$. Also, it is difficult, and pointless, to analyze everything exactly. Big O notation hides all these details while keeping the nucleus, which is the asymptotics of the running time. As an example, since quicksort is $O(n\log n)$ while insertion sort is $O(n^2)$, you should expect the former to outperform the latter for large values of $n$. (Of course, it all depends in practice on the so-called hidden constants.)
answered Jan 24, 2014 at 3:27