a. Count the number of multiplication as basic operation, and state the Big-Oh f

Question

a.       Count the number of multiplication as basic operation, and state the Big-Oh for each complexity. Prove only how did you get the big-Oh only for part 1.

b.      Implement the code in the language of your choice, and find the running time for several values of N.

             C . Compare the theoretical time complexity with the actual running times

1.

product = 1;

for (i = 1; i <= n; i++)

product*=i;

2.

product = 1;

for (i = 1; i <= n; i++)

for (j = 1; j <= i; j++)

product*=j;

3.

product = 1;

for (i=1; i<=n ; i++)

for (j = 1;  j <= i; j++)

        for (k = 1;  k <= j;  k++)

product*=k;

  Put the following recurrence relations into closed forms:

a.       T(n) = 3T(n-1) -15

T(1) = 8

b.      T(n) =  T(n-1) + n -1

T(1) = 3

c.       T(n) =  6T(n/6) + 2n + 3  for n a power of 6.

T(1) = 1

Use the Master Method to find the approximate solution for the following recurrence relations. Be sure to  identify the values of a, b, and d in your answer.

a.        T(n) = 5 * T(n/4) + n -3

b.      T(n) = 9*T(n/3) + n2 + 4

c.       T(n) = 6 *T(n/2) + n2 -2

Explanation / Answer

1)

product = 1;

for (i = 1; i <= n; i++)

product*=i;

in each iteration of the loop there is 1 multiplication.

and since loop iterate for n times so total number of multiplication = n;

step count

statement -------------- count

product = 1; 1

for (i = 1; i <= n; i++) n+1

product*=i; n

so total count =f(n)= 1 + (n+1) +n = 2n+2

As we know that f(n) is said to be Big-Oh(g(n))

iff |f(n)|<=c*g(n) for all n>=n0 , where c and n0 are constants

f(n)=2n+2

==> |f(n)| <= 2n+n for all n>=2

==>|f(n)| <= 3n for all n>=2

hence f(n) = Big-Oh(n) where c=3 and n0=2

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.