3,065 views
4 votes
4 votes

Determine the time complexity of the program segment given below:

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

(A) O(n2)
(B) O(n.log n)
(C) O(log2 n)
(D) O(log n√n)

1 Answer

0 votes
0 votes
while loop runs independently for logn times.

now for loop

k value= 1 2 3 4  5  ...............................

j value=  1 3 6 10 15 .............................

 

here

t[1]=1

t[2]=t[1]+2=1+2=3

t[3]=t[2]+3=2+3=5

.

.

.

t[j]=t[j-1]+j

here j executes k times

so, k(k-1)/2 <=n

O(k^2)<=n

k<=O(n^1/2)

there fore ans is O(root n logn)
Answer:

No related questions found