14,978,669 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!!!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 OriginalGriff 213 Richard Deeming 35 Code Fan 35 Patrice T 35 Adérito Silva 30
 OriginalGriff 5,356 Richard MacCutchan 2,567 Richard Deeming 2,043 Patrice T 1,135 Dave Kreskowiak 963

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900