Time complexity on nested for loop

Question

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))?

Eloy Pérez Torres · Accepted Answer · 2020-09-22 04:58:16Z

3

The correct summation according to the code is:

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

answered Sep 22, 2020 at 4:58

Eloy Pérez Torres

1,1777 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

abc · Accepted Answer · 2020-09-20 09:22:57Z

2

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)

edited Sep 20, 2020 at 9:22

answered Sep 20, 2020 at 9:07

abc

12k2 gold badges30 silver badges55 bronze badges

Collectives™ on Stack Overflow

Time complexity on nested for loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related