CODEWITHSUNDEEP
time-complexity
Auclown
Auclown

Reputation: 308

Time complexity of this code?

So these are the for loops that I have to find the time complexity, but I am not really clearly understood how to calculate.

for (int i = n; i > 1; i /= 3) {
    for (int j = 0; j < n; j += 2) {
    ... ...
    }
    for (int k = 2; k < n; k = (k * k) {
    ...
    }
}

For the first line, (int i = n; i > 1; i /= 3), keeps diving i by 3 and if i is less than 1 then the loop stops there, right?

But what is the time complexity of that? I think it is n, but I am not really sure. The reason why I am thinking it is n is, if I assume that n is 30 then i will be like 30, 10, 3, 1 then the loop stops. It runs n times, doesn't it?

And for the last for loop, I think its time complexity is also n because what it does is

k starts as 2 and keeps multiplying itself to itself until k is greater than n.

So if n is 20, k will be like 2, 4, 16 then stop. It runs n times too.

I don't really think I am understanding this kind of questions because time complexity can be log(n) or n^2 or etc but all I see is n.

I don't really know when it comes to log or square. Or anything else.

Every for loop runs n times, I think. How can log or square be involved?

Can anyone help me understanding this? Please.

Upvotes: 0

Views: 121

Answers (1)

Dylan Brams
Dylan Brams

Reputation: 2099

If you want to calculate the time complexity of an algorithm, go through this post here: How to find time complexity of an algorithm

That said, the way you're thinking about algorithm complexity is small and linear. It helps to think about it in orders of magnitude, then plot it that way. If you take: 

x, z = 0
for (int i = n; i > 1; i /= 3) {
    for (int j = 0; j < n; j += 2) {
    x = x + 1
    }
    for (int k = 2; k < n; k = (k * k) {
    z = z + 1
    }
}

and plot x and z on a graph where n goes from 1 -> 10 -> 100 -> 1000 -> 10^15 or so, you'll get an answer which looks like an n^2 graph. When analyzing algorithmic complexity you're primarily interested in maximum the number of times, in either the worst or most common case, your inputs are looped through omitting constants. So in this case I would expect your algorithm to be O(n^2)

For further reading, I suggest https://en.wikipedia.org/wiki/Introduction_to_Algorithms ; it's not exactly easy but covers this in depth.

Upvotes: 1

Related Questions