How can we find the Time Complexity of the Algorithm

user_14485433 0
Viewed 43

I want to know about the time complexity of the given code below, I have a doubt it is O of root n

i = n, sum = 0
while (i >= 0){
    i /= 2
    sum += i*i*i
}

I am really confused can anyone help me out and explain

algorithm
2 Answers

If you're unsure you can always use "time" module to roughly get an idea of the complexity. It would go something like this.

import time

start = time.time() # put this before the loop

end = time.time() #put this after the loop

print(end - start) #this gives you evaluation time of your loop

Find evaluation times for different n's and determine the complexity.

Just by looking at it though, your loop gets executed roughly log2(n) times, and inside you have 2 multiplications and one division (so nothing complex). Therefore, I would assume O(log(n)) is a reasonable guess.

user_164016270

As mentioned in the comments, I'm assuming that the code was meant to be written as

i = n, sum = 0
while (i > 0) { // <--- Change >= to >
    i /= 2
    sum += i*i*i
}

since otherwise the code would be an infinite loop. With this in mind, let's take a look at what this code is doing.

For starters, note that the sum variable isn't doing anything that impacts our time complexity. On each iteration, it gets bigger, but we're doing only O(1) work to update it. That means that the time complexity here is going to depend on how many times the loop runs. Notice that, across the different iterations of the loop, the value of i will take on the sequence

n, n / 2, n / 4, n / 8, n / 16, n / 32, ...

and, in particular, on the kth iteration of the loop the value of i will be equal to n / 2k (ignoring rounding down, which we can safely do here). The question, then, is at what iteration of the loop we end up with n / 2k < 1, which is when the loop will stop. Solving, we get that

n / 2k < 1

n < 2k

log2 n < k

So this loop will stop as soon as the number of loop iterations k is greater than log2 n. This means that we do Θ(log n) loop iterations, of which each iteration does O(1) work, so the total work done is Θ(log n).

user_5015570
Related