1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What did the person who gave you the exercise say when you asked them? $\endgroup$ May 10 at 4:47

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.