CODEWITHSUNDEEP
time-complexity
Brody_Brody
Brody_Brody

Reputation: 315

Time complexity on nested for loop

function(n): 
{
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n / 2; j++)
            output("")
    }
}

Now I have calculated the time complexity for the first for loop which is O(n). Now the second for loop shows j <= n / 2 so any given n I put, for example, a range of [1,2,...,10] will give me O(log(n)) since it will continuously give me a series of n,n/2,n/4,n/8 .... K.

So if we wanted to compare the relationship it must look something like this 2^n = k.

My question is will it give me O(log(n))?

Upvotes: 0

Views: 177

Answers (2)

Eloy P&#233;rez Torres
Eloy P&#233;rez Torres

Reputation: 1177

The correct summation according to the code is:

1

So, it's not O(log n). It's O(n^2).

Upvotes: 3

abc
abc

Reputation: 11929

No, it does not give you o(logn).
The first for loop is O(n). The second loop is O(n) as well, as the number of iterations grows as a function of n (the growth rate is linear).
It would be the same even by changing the second loop to something like

for (j=1; j<=n/2000; j++)

or in general if you replace the denominator with any constant k.
To conclude, the time compexity is quadratic, i.e., O(n^2)

Upvotes: 2

Related Questions