2.5

Define [math]g(k)[/math] as the number of times the inner loop executes for a fixed [math]k[/math]. Because the value [math]x[/math] doubles each iteration, the loop stops after [math]g(k)=\lceil\log_{2}(n/k)\rceil[/math] iterations (for [math]k<n[/math]; for [math]k=n[/math] it is 0). Hence [math]f(n)=\displaystyle\sum_{k=1}^{n-1} g(k).[/math]

Partition the indices into powers of two: for [math]i\ge 1[/math] let  [math]A_i=\{\,k \mid n/2^{\,i}. The size of this block is [math]|A_i|=n/2^{\,i}[/math] and every [math]k\in A_i[/math] prints exactly [math]i[/math] asterisks, so [math]\displaystyle f(n)=\sum_{i=1}^{\lceil\log_{2}n\rceil} i\cdot|A_i| = n\sum_{i=1}^{\lceil\log_{2}n\rceil}\frac{i}{2^{\,i}}. [/math]

The geometric-like series [math]\sum_{i\ge1} i/2^{\,i}=2[/math] is bounded above and below by positive constants, so [math]n \le f(n) \le 2n.[/math]

Therefore the number of printed asterisks grows linearly: • upper bound: [math]f(n)=O(n)[/math] • lower bound: [math]f(n)=\Omega(n)[/math] Combining them gives the tight bound [math]f(n)=\Theta(n).[/math]

Back to Chapter 2