CODEWITHSUNDEEP
algorithmmathtimecomplexity-theorycode-analysis
Red
Red

Reputation: 2246

Run times for while loop (Mathematical)

So I need a mathematical expression for the following loop, but I can't seem to grasp it. I am assuming I am just missing something simple. 

while a <= b
    a = a + a
end

Using an analysis, what would be the run time of this function?

Upvotes: 1

Views: 12785

Answers (3)

Keith Randall
Keith Randall

Reputation: 23265

Since you're doubling a every time, you need log(b/a) doublings before the loop will exit. So the run time is Theta(log(b/a)).

Upvotes: 1

thb
thb

Reputation: 14434

Would you agree that each iteration of the loop doubles a? If so, then let a have an initial value of 1. After one iteration, a == 2. After two iterations a == 4. After three, a == 8. After four, a == 16; and so on.

Suppose that b == 64. The loop will run seven iterations in this case. Observe that log_2(64) == 6.

Suppose that b == 128. The loop will run eight iterations in this case. Observe that log_2(128) == 7.

Suppose that b == 256. The loop will run nine iterations in this case. Observe that log_2(256) == 8.

Therefore, the run time depends on the logarithm of b.

Upvotes: 1

paxdiablo
paxdiablo

Reputation: 881253

The run time is dependent on the logarithm of b. In other words, the time complexity is O(log N).

You can see this if you start a at 1 and b at 256. Each time through the loop, a is doubled so that there are only nine iterations (would be eight if the condition was < b).

Each doubling of the b value will result in one extra iteration.

Of course, this is complexity analysis, the runtime depends on a host of other factors such as (almost certainly not an exhaustive list):

  • how fast your machine is.
  • what other things it has to do concurrently.
  • initial value of a: a == 0 gives infinite run time, a == b + 1 gives you constant run time.

Upvotes: 3

Related Questions