Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm.
This is what I'm struggling to understand, I think I know how to recognize what's the runtime using the big O Notation as it's only a nested loop but what is exactly an exact runtime?
How am I supposed to calculate it? How would that look like with a simple bubble sort algorithm?
Consider the bubble sort algorithm shown below:
function sort(A)
n = A.length
for i = 1 to n-1
for j = n downto i+1
if A[j] < A[j-1]
swap A[j] with A[j-1]
One way to measure the performance of this algorithm is to count the number of swaps performed by the algorithm. For the worst-case input, the number of swaps performed by the algorithm is $(n-1)+(n-2)+\cdots+2+1 = n(n-1)/2$. This is the exact number of swaps performed in the worst-case.
In the worst case, the number of swaps performed by the algorithm is $O(n^2)$. This expression uses asymptotic notation to describe the worst-case performance.
You can’t calculate any runtime except for some very simple model of a CPU. You can calculate the exact number of comparisons, or the exact number of operations moving array elements of a particular implementation of an algorithm, but it’s practically impossible to predict how many seconds or microseconds the algorithm will run for.
If nothing precise was specified, you can enumerate all operations by type, such as addition, comparison, swap... and give a detailed account of their numbers. That assumes the the basic operations take some constant (but unknown) time each.
In practice, you prefer to limit the evaluation to a single type of operation, such that the other operations are performed in at most a proportional amount.
