edited by
702 views
1 votes
1 votes

Determine the time complexity of the program segment given below:

k = n;
while ( k > 0)
{
    i = 1;
    for(j = 1; j <= n; j+=i)
        i++;
    k/=2;
}
  1. $\Theta\left(n^2\right)$
  2. $\Theta(n \log n)$
  3. $\Theta(\log^2 n)$
  4. $\Theta\left(\log n \sqrt n\right)$
edited by

1 Answer

Best answer
12 votes
12 votes
The outer loop executes $\Theta(\log n)$ time as $k$ goes from $n, n/2, \dots 0$. The inner loop is bit tricky.

The $j$ values goes like

$1, 1+2, 1+2+3, 1+2+3+4, \dots n$

This means j loop iterates $\Theta(\sqrt (n)) $ times as it eventually stops when the sum of first $k$ integers $(\frac{k.(k+1)}{2})$ goes above $n$.

So, overall time complexity is $\Theta \left( \log n \sqrt n \right)$
selected by
Answer:

Related questions

3 votes
3 votes
0 answers
1
1 votes
1 votes
2 answers
2
akankshadewangan24 asked Sep 20, 2018
843 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 votes
0 votes
3 answers
3
Subham Nagar asked Mar 20, 2018
1,185 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 votes
0 votes
0 answers
4
Kai asked Jan 29, 2017
423 views
Time complexity of the given program is?