Homework 1
due Mon 1/29 in class

1. Order the following functions by growth rate, from slowest-growing to fastest growing. Provide justifications for your answer.

   • n² log₂ n
   • n (log₂ n)²
   • Σ_i=0..n 2ⁱ
   • log₂ ( Σ_i=0..n 2ⁱ )

2. Give the worst-case running time for each of the following sets of loops. Remember that the total time for a loop is the sum of the time for each iteration - write the sum(s) and use the sums table to get the big-Oh for each. Assume that the ... steps take Θ(1) time.

   1.     for i = 1 to n do
            ...
        

   2.     for i = 1 to n do
            for j = 1 to i do
              ...
        

   3.     for i = 1 to n do
            for j = 1 to i do
              for k = j to i+j do
                ...
        

   4.     for i = 1 to n do
            for j = 1 to i do
              for k = j to i+j do
                for m = 1 to i+j-k do
                  ...