Search code examples
algorithmsequences

Find the relationship between input and number of times a loop executes.

Given this code: 

k = 1;
p = 0;
while (k < n){
  k *= 3;
  p++;
}

Define the number of times line 03 will execute in terms of n, where n is the input. (Hint: Find out how p and k are related to n at the end of the loop in line 06. Express p in therms of n and use that to answer this question.)

So far what I've done is figured out the number of times p and k execute related to these values of n:

  • n = 1 -> k/p iterations = 1
  • n = 3 -> k/p iterations = 3
  • n = 10 -> k/p iterations = 3
  • n = 30 -> k/p iterations = 4

I'm struggling to figure out how to define a relationship between n and the number of iterations for k/p. If someone could please explain how to determine this it would be greatly appreciated.

Solution

  • You've approached this problem by trying out a couple of different examples and looking to see if you can spot a pattern. That's a reasonable approach to take, but it's a bit tricky to get working. Instead, you might want to look at the values that k takes on as the loop iterates and see if you can work from there.

    Notice that k grows exponentially as a function of the number of loop iterations: it takes on the values 1, 3, 9, 27, 81, ... . Written differently, it takes on the values

    30, 31, 32, 33, 34, etc.

    And, more generally, on loop iteration i, it takes on the value 3i.

    Given that this loop stops as soon as k is greater than or equal to n, we can work out how many loop iterations there will be by solving for the smallest value of i for which 3i ≥ n. We can do that as follows:

    3i = n

    i = log3 n

    This number might not be a whole number, so we'll round up by taking the ceiling and say that the number of iterations is ⌈log3 n⌉.

    Generally speaking, if you see some process that works by repeatedly growing by a constant factor (always tripling, or always doubling, or always going up by a factor of 10, etc.) you should expect to see some kind of logarithmic term show up. That's one of the most common ways you see O(log n) show up.