CODEWITHSUNDEEP
algorithmtime-complexity
Julius Limson
Julius Limson

Reputation: 526

time complexity (with respect of n input)

I was asked if what time complexity if this:

What is the time complexity (with respect of n) of this algorithm:

k=0
for(i = n / 2 ; i < n ; i++ ) {
   for( j=0 ; j < i ; j++)
      k = k + n / 2
}

choices was : a. O(n) b. O(n/2) c. O(n log(n) and d. O(n^2)

can have a multiple answers.

i know the algorithm above is d. O(n^2) but i came with with a. O(n) since it is looking for complexity of n only?.

if you are to have this question. how would you answer it.?? im so curious about the answer.

Upvotes: 0

Views: 112

Answers (1)

sanketd617
sanketd617

Reputation: 809

The answer is O(n²).

This is easy to understand. I will try to make you understand it.

See, the outer for loop block is executed n - n/2 = n/2 times.

Of course it depends whether the number n is even or odd. If it's even then the outer loop is executed n/2 times. If it's odd then it's executed for (n-1)/2 times.

But for time complexity, we don't consider this. We just assume that the outer for loop is executed n/2 times where i starts from n/2 and ends at n - 1 (because the terminating condition is i < n and not i <= n).

For each iteration of the outer loop, the inner loop executes i times.

For example, for every iteration, inner loop starts with j = 0 to j = i - 1. This means that it executes i times (not i - 1 times because j starts from 0 and not from 1).

Therefore, for 1st iteration the inner loop is executed i = n / 2 times. i = n / 2 + 1 for 2nd iteration and so on upto i = n - 1 times.

Now, the total no. of times the inner loop executes is n/2 + (n/2 + 1) + (n/2 + 2) + ... + (n - 2) + (n - 1). It's simple math that this sums up to (3n² - n)/2 times.

So, the time complexity becomes O((3n² - n)/2).

But we ignore the n term because n² > n and the constant terms because for every n they will remain the same.

Therefore, the final time complexity is O(n²).

Hope this helps you understand.

Upvotes: 1

Related Questions