This question already has an answer here:

I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me.

the loop is

for(j=1; j< n; j=j*2)

J is increasing at an increasing rate so it will be less than n/2 however I am having trouble concluding what exactly it will be.


marked as duplicate by David Richerby, Raphael Nov 3 '15 at 6:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? In particular, see the section "While-Loops" in this answer. The example loop there is essentially identical to this one, except that the loop in this question "counts up", whereas that one counts down. $\endgroup$ – David Richerby Nov 3 '15 at 0:38
  • $\begingroup$ That is probably a way over complicated answer. Also I don't fully follow it. Nor does it seem to give the answer i was looking for. I was hoping for something like a log n and an explanation why. That seems to be more of logic for a for loop and not the run time specifically for j=j*2 and if it is then I am sorry I just didn't follow the math myself $\endgroup$ – Peter3 Nov 3 '15 at 0:48
  • $\begingroup$ Welcome to the site! You're right in observing that our "reference questions" aren't as immediately helpful as they could be. Because they are intended to be useful for a wide range of questions about a topic, they necessarily have a lot of detail that might actually obscure the answer a visitor needs. This is a decision that was made a while ago and while some of us aren't happy about it, it's just what we have to deal with. If you stick around here you'll find that you might have a better chance of getting useful help if you ask sharply defined and limited questions. Best of luck. $\endgroup$ – Rick Decker Nov 3 '15 at 1:26
  • 1
    $\begingroup$ The reference question contains examples, and there are more under algorithm-analysis+loops. Closing your question because you don't say what you tried, specifically, and where you did get stuck. $\endgroup$ – Raphael Nov 3 '15 at 6:45

In your loop, $j$ will take the values $1, 2, 4, 8, \dotsc, 2^k$ where $2^k<n$. You need to know how many times this will iterate. In other words, what will be the largest $k$ for which we have $2^k < n$? Take the log to the base 2 of each side of the inequality and you're asking what the largest $k$ will be for which $k<\log_2n$. What this means is that you're right in your comment: the loop will iterate no more than $\log_2n$ times.


Not the answer you're looking for? Browse other questions tagged or ask your own question.