Question

Q 7: What is the number of `Hello's printed by the pseudo code below? (for i from lo to hi
exhaust i between lo and hi inclusive, and is a empty loop when lo is greater than hi)

(a) for i from 1 to n
for j from 1 to i - 1
for k from 1 to j - 1
print `Hello'

(b) for i from 1 to 10
for j from i to 10
for k from i to j
print `Hello'

Answer 1

Assuming that k from 1 to n fails to execute if n < 1,

when i=1, j fails
when i=2, k fails at j=1
when i=3, j=1..2, k=0+1..1=1
when i=4, j=1..3, k=0+1+2=3
when i=5, j=1..4, k=0+1+2+3=6
...
when i=n, j=1..n-1, k=0+1+2+...+n-2 = (n-2)(n-1)/2

so, the total prints executed is
1+3+...+(n-2)(n-1)/2
= (n-2)(n-1)(n)/6

now do a similar analysis on (b)