Click here to Skip to main content
15,028,757 members
Please Sign up or sign in to vote.
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

1 solution

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)




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