Give the best possible asymptotic answer to each recurrence.

1.  f(n) <= n^2 + 2f(n/2)

2.  f(n) = Theta(log n) + f(n/2)

3.  f(n) = Omega(n) + f(n-1)

4.  f(n) <= 5n + f(n/2)

5.  f(n) = 2f(n/4) + 1

6.  f(n) >= n/2 + 3f(n/3)

7.  f(n) = f(log n) + 1

8.  f(n) = f(n-1) + 1/n

9.  f(n) <= 2f(sqrt(n)) + log n

10.  f(n) <= 2f(n-1) + 3f(n-2)

For each block of code, give the best possible asymptotic answer, in
terms of n, for the time for the code to execute.

11.  for i from 1 to n do
      for j from 1 to i do
       "hi"

12.  m = n
     while m > 0 do
      m = min(m-1,george(m))  Comment: george is an unknown function
                              Comment: The execution time for george is O(1)

13.  proc martha(n)
      if n > 1
       martha(n/2)

14.  proc bonnie(n)
      if n > 1
       {
        bonnie(n/2)
        bonnie(n/2)
       }

15.  proc clyde(n)
      if n > 1
       {
        clyde(n-1)
        clyde(n-1)
       }

16.  for i from 1 to n
      {
       m = 1
       while m < i
        m = 2m
      }

17.  for i from 1 to n
      {
       m = i
       while m < n
        m = 2m
      }

18.  m = n
     while m > 1
      m = m - sqrt(m)