Made Easy Example 1.8

Question

What is the total no of multiplications to be performed??

D=2

For i=1 to n do

    For j=i+1 to n do

       For k=j+1 to n do

          D=D×3

Comments

O(n^3).?

Answer 1

for(i=1 to n)

  for(j=i+1 to n)

    for(k=j+1 to n)

For n=0; mult=0;

for n=1;mult=0;

for n=2; mult=0;

for n=3;mult=1;   for n=4;mult=4     and n=5 mult=10;[putting n checked no of iteration satisfied for multiplication;

For gen it must contain n,(n-1),(n-2) as factor so by so checked for general formula for n terms.

no of multiplication =[n*(n-1)*(n-2)/6]