CODEWITHSUNDEEP
algorithm
Saiyan
Saiyan

Reputation: 197

Running time of algorithm in worst case

What's the running time of the following algorithm in the worst-case, assuming that it takes a constant time c1 to do a comparison and another constant time c2 to swap two elements?

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n - 1; j++)
    {
        if (array[j] > array [j+1])
        {
            swap(array[j], array[j+1]);
        }
    }
}

I get 2+4n^2. How I calculate it (starting from the inner loop):

The inner loop runs (n-1) times.
The first time it runs, there is the initialisation of j and the comparison of j with (n-1) to know whether to enter the loop. This gives 2 instructions.
Each time it runs, there is the comparison of j with (n-1) to know whether to continue the loop, the increment of j, the array comparison and the swapping. This gives 4 instructions which run (n-1) times, therefore 4(n-1) instructions. The inner loop thus contains 2+4(n-1) instructions.

The outer loop runs n times.
The first time the outer loop runs, there is the initialisation of i and the comparison of i with n. This gives 2 instructions.
Each time it runs, there is the comparison of i with n, the increment of i and the inner loop. This gives (2+(2+4(n-1)))n instructions.

Altogether, there are 2+(2+(2+4(n-1)))n instructions, which gives 2+4n^2.

Is it correct?

Upvotes: 0

Views: 526

Answers (1)

Adam Evans
Adam Evans

Reputation: 2082

You forgot to account for the addition of j+1 for the index in the if statement and the swap call, and the n-1 calculation in the inner for loop will be an extra instruction.

Remember, every calculation counts as an instruction, which means that essentially every operator in your code adds an instruction, not just the comparisons, function calls, and loop control stuff.

for (int i = 0; i < n; i++)               //(1 + 1) + n(1 + 1 + innerCost)          (init+comp) + numLoops(comp+inc+innerCost)
{
    for (int j = 0; j < n - 1; j++)       //(1 + 2) + (n-1)(1 + 1 + 1 + inner)      (init+comp) + numLoops(sub+comp+inc+innerCost)
    {
        if (array[j] > array [j+1])       //1 + 1        (1 for comparison, 1 for +)
        {
            swap(array[j], array[j+1]);   //1 + 1        (1 for function call, 1 for +)
        }
    }
}

runtime = (1+1) + n(1+1+ (1+2)+(n-1)(1+1+1+ (1+1 + 1+1)))

runtime = 2 + n( 2 + 3 +(n-1)( 3 + 2 + 2))

runtime = 2 + n( 5 +(n-1)(7))

runtime = 2 + n( 5 + 7n - 7)

runtime = 2 + n(7n-2)

runtime = 2 + 7n^2 - 2n = 7n^2 - 2n + 2

Upvotes: 2

Related Questions