15,030,240 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).
Comments
_-_-_-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 228 Richard Deeming 125 CHill60 95 keithd1965 60 CPallini 50
 OriginalGriff 2,312 Richard Deeming 1,563 Richard MacCutchan 1,117 CPallini 890 Patrice T 550

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