15,034,986 members
1.00/5 (1 vote)
See more:
What is the time complexity for this programme ?

I calculated it like this:
p is noumber of runs

n/(2 power p) = (2 power p) (could we keep "=" here?)

n = (2 power p)(2 power p)
n= 2^2p

p= (logn(base2))^1/2

Time complexity is O((logn(base2))^1/2)

Is it correct? Can we keep equal "=" there ?(As in the program it was given that i<n).

<b>What I have tried:

C++
```void fun(int n)
{
int i=1;
while(i<n)
{
int j=n;
while(j>0)
j=j/2;
i=2*i;
}
}```
Posted
Updated 9-May-21 6:33am

## Solution 1

The number of times you can double a starting value of 1 to get n or more is the same as the number of times you can halve a starting value of n before you get a value less than 1. Either way, the number of steps is log2(n).

So the outer loop runs O(log n) times and each instance of the inner loop runs O(log n) times. The total time is O(log n)^2 = O((log n)^2) = O(log^2 n).
_-_-_-me 9-May-21 13:36pm

Thank you. Does the base of the logorithm contain 2 ?
mike@codeproject 9-May-21 14:32pm

The base of a logarithm doesn't matter in big-O or big-theta notation. O(log x) = O(ln x) = O(lg x) = O(log_b x)
mike@codeproject 9-May-21 14:36pm

... since log_a(x) = log_b(x) * (1 / log_b(a)) for any bases a > 1 and b > 1.
_-_-_-me 9-May-21 14:50pm

Thank you very much for your help!!!