Counting the innermost calls

For $n = 16$ , exactly how many times does work() execute in this fragment?

for (i = 1; i <= n; i++)
  for (j = 1; j <= n; j++)
    for (k = 1; k <= n; k *= 2)
      work();

Show hints (2)+

The two outer loops each run $16$ times; the inner one does not - k doubles.
Count the powers of two in $[1,16]$ : $1,2,4,8,16$ . Then multiply the three counts.

Answer

Reveal answer →

1280

Create a free account to see the full worked solution and track your progress.