Sample Test

1. Consider the following code fragments.  In each case, assume that the
value of n is a given positive integer.

sum = 0;
for { i = n; i > 1; i /= 7 }
   sum++;

sum = 0;
for { i = 0; i < n; i++ }
  for { j = i; j > 1; j /= 2 }
     sum++;

sum = 0;
for { i = 1; i < n; i++ }
  for { j = 0; j < n; j+=i }
     sum++;

What is the asymptotic time complexity, in terms of n, of each fragment?
Give sharp answers.  (You do not need to prove your answers.)

2.  Give a formal proof, from the definition of "big O",
that 5n^2 + 7n + 100 = O(n^2).

3.  You learned how to multiply numbers in grade school (I think it was
in the fourth grade in my school.)  What is the asymptotic time complexity
of the "grade school algorithm" for multiplying large numbers?

4.  Most people think that Quicksort has asymptotic time complexity
O(n log n).  But, in class we stated that it does not.  Explain what we
mean by that.