• edited by
1,729 views
1 1 vote

1 Answer

1 1 vote
Take , n=5 (say) and see what values j assumes. You will find that , j assumes values like 1,3,6 for k=1,2,3 , thus j assumes values like k(k+1)/2. Now the for loop runs for k times , and j=k(k+1)/2, so equating with n on RHS , k^2=n or k=sqrt(n). So for loop runs sqrt(n) times.
Outer while is of the form [where i=n]

while(i>0){
i=i/2
} and so complexity is log n. Hence for each of these log n times the for runs sqrt(n) times , complexity=O(logn*sqrt(n)).
Position:
Show:

Related questions

1 1 vote
2 2 answers
1.7k
1.7k views
akankshadewangan24 asked Sep 20, 2018
1,714 views
If t(n) and s(n) denotes the time and space complexity of an algorithm with input size n element then which one of the following is always true?S(n)=O(t(n)) correct H...
0 0 votes
3 3 answers
3.2k
3.2k views
Subham Nagar asked Mar 20, 2018
3,237 views
An array $'A'$ has $n$ distinct integers. What is the tightest time complexity to check $A[i]=i$ for some $i$. Consider all elements of array within range from $1$ to $n$...
0 0 votes
0 0 answers
744
744 views
Kai asked Jan 29, 2017
744 views
Time complexity of the given program is?
1 1 vote
1 answers 1 answer
1.5k
1.5k views