Complexity of While Loop

[Chris Jones]

*Sorry if this is a duplicate, I am trying to figure it out*

Does anyone know how to explain more in depth how we find the
complexity of a while loop?

Thanks

[cs240]

Can you specify the problem in more detail? "A while loop" is a general
term and can be used in so many different kinds of algorithms.

Usually the complexity of a loop is expressed as the sum of the
complexities of each iteration. So to get started, you may want to count
the number of iterations the while loop runs.

Vivian
CS240 Tutor

Post by Chris Jones
*Sorry if this is a duplicate, I am trying to figure it out*
Does anyone know how to explain more in depth how we find the
complexity of a while loop?
Thanks

[Chris Jones]

say you have the following code

while n >= 1
n = n/2
end while

I know it is of logarithmic time from class, but I did not
specifically understand how they got to that conclusion. (I think I
made a mistake in my notes)

I am trying to work on Q4 from A1, and I know its true, just having
troubles in some of the proof.

Thanks

[cs240]

First of all, the assignment operation inside the loop takes constant time
under the RAM model. So the complexity of this loop depends on the number
of iterations that the loop runs. Following the algorithm, the value of n
goes like this:

n, n/2, n/(2^2), n/(2^3), ..., 1

The loop stops after i iterations when n is 1, that is

n/(2^i) = 1

Solve this equation for i, then you have

i = log n

Therefore the while loop runs log n times, each iteration takes constant
time, therefore the while loop has a complexity of theta of log n.

Vivian
CS240 Tutor

[Chris Jones]

Thanks a lot, I get it now!