Algorithm Analysis Homework

1.   Arrange the following from slowest growth to fastest growth.
        4n²     log₃n    3ⁿ     20n     2     log₂n     n^2/3

2.    Suppose we have an algorithm that takes time 2ⁿ.  Let the algorithm process n inputs in T seconds on machine M.  How much time would it take for a machine that is 64 times faster? (part 2) what if the algorithm take time n²?  (part 3)  what if the time complexity is n?

3.    Determine the big O for the following code groups:

a.        for (i=0; i<3; i++)
                for (j=0; j<n; j++)
                      sum++;

b.        for (i=0; i<n*n; i++)
                sum++;

c.        for (i=0; i<n; i=i+2)
                for (j=0; j<n; j++)
                    sum++