CSE 2321 HOMEWORK 7

1.   Determine the running time of the following algorithm. Write summations to represent loops and solve using bounding. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer.

Func1(n)

1       s  ←  0;

2       for i  ←  nton2  do

3             for j  ←  1 to i do

4                   fork  ←  9n to 10n2  do

5                      form  ←  itok

6                                   s  ←  s  +  i   − j  +  k − m;

7                          end

8                    end

9             end

10     end

11     return (s);

2.   Find the running time for each of the following algorithms. Show work by finding a table of values for each while loop, writing the summations, then solving. Be sure to show work on both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer.

a)   Func2(n)

1       s  ←  0;

2       j  ←  7n2 ;

3       while (j  >  8) do

4              s  ←  s  +  i  − j;

5              j  ←  ⌊j/9⌋;

6       end

7       return (s);

b)  Func3(n)

1       s  ←  0;

2       i  ←  n;

3       while (i  < 5n3) do

4           j  ←  7n2 ;

5             while (j  >  8) do

6                  s  ←  s  +  i  − j;

7                  j  ←  ⌊j/9⌋;

8              end

9             i  ←  4  ×  i;