CODEWITHSUNDEEP
algorithmtime-complexity
template boy
template boy

Reputation: 10490

What is the running time of the following program?

The exercise in my book is asking me to calculate the running time of the following for loop:

for (int i = 0; i < n; ++i)
    ++k;

This instantly reminds me of summation notation. So I write down the appropriate syntax:

enter image description here

Is this correct? If not, why not - and how can I calculate it correctly?

Upvotes: 0

Views: 344

Answers (2)

haccks
haccks

Reputation: 106122

Is this correct?

No. It is not.

If not, why not - and how can I calculate it correctly?

k is incremented by 1 in each iteration, i.e n is added to it when loop terminates. So, k = k + 1 is not equal to k = k + k.

Running time of the code is of order n because the loop runs n times and ++k is done in constant time inside the loop.

Upvotes: 2

Bill Lynch
Bill Lynch

Reputation: 82026

Let's look at the operation inside the loop:

++k;

No matter what k is, that operation will take constant time. So let's replace it with O(1).

for (int i=0; i<n; ++i)
    O(1)

We can see that we are going to iterate over the O(1) block n times. So that is:

O(n) * O(1)

Which is clearly equal to:

O(n)

Upvotes: 0

Related Questions