1. Exercise 9.2 of Aho, Hopcroft, and Ullman. Solve the following recurrances, where T(1) = 1, and T(n) for n>=2 satisfies:
    (c) T(n) = 8T(n/2) + n3
    "Solve" means "guess a solution and prove it is correct using induction." Assume that n is a power of 2. You may also note the following hints for the respective parts:

    Without seeing the general solution in Chapter 3 yet, but having seen the solution for problem (a) and the hint, a good guess is T(n) < cn3log n + bn3
    Particularly n3log n + n3

    Prove using induction:

    PROOF:

    Base:
    T(1) = 1 by definition
    T(1) < c*13log 1 + b*1 (assume logs are always base 2) implies
    1       <       0 + b       implies let
    b = 1

    Induction hypothesis:
    Assume THM is true: T(n) = 8T(n/2) + n3 < cn3log n + n3 for all n < n'.

    Induction step:

    Choose n = n' + 1

    T(n) = 8T(n/2) + n3 (is the definition of T(n))

    since n/2 < n', by induction hypothesis T(n/2)< c(n/2)3log(n/2) +(n/2)3 ,
    T(n) = 8T(n/2) + n3 and substituting in for T(n/2) we see
     T(n) < 8[c(n/2)3 log(n/2) + (n/2)3] + n3

    < 8[(cn3/8) log(n/2) + n3/8] + n3
    < cn3(log n - log 2) + n3 + n3
    < cn3log n - cn3 + 2n3
    with c=1,
    < n3log n + n3

    is O(n3log n)

  2. i=0 to n 2i
    = 1+ 2 + 4 + 8 + ...+ 2n
    n Summation exponentially
    0 20 = 1 21-1
    1 20 + 21 = 3 22-1
    2 20 + 21+22= 7 23-1
    3 20 + 21+22+23=15 24-1

    = 2n+1 - 1

    Proof

    Base:
    i=0 to 0 2i =20 = 1
    2n+1 - 1 = 20+1 - 1 = 2-1 = 1

    Assumption:
    i=0 to n 2i = 2n+1 - 1 for n0 < n

    Proof
    SHOW true for n + 1, i.e.,
    i=0 to n+1 2i = 2n+2 - 1

    i=0 to n+1 2i
    = 1+ 2 + 4 + 8 + ...+ 2n + 2n+1
    =(i=0 to n 2i) + 2n+1
    by inductive assumption
    = (2n+1 - 1) + 2n+1
    = 2(2n+1) - 1
    = 2n+2 - 1

  3. Order:

    n-1      <       n/log n       <       2log2n       <       nlog n       <       n2

    Def. f(n) = O(g(n)) iff there exists positive constants c and no such that f(n) < cg(n) for all n , n > no

    iff there exists positive constants c1, c2 and no such that c1g(n) < f(n) < c2g(n) for all n , n > no

  4. Show that the following inequalities are correct:

  5. Show that the following inequalities are incorrect:
      Note that for proving inequalities do not hold, it is not sufficient simply to find specific c's and n's that do not work since I may be able to find a c or n that does. Hence, you need to show that sooner or later any choice of c will have a problem. This is usually done by considering the fact that the statement must be true "for all n, n > n0"
      Specifically, that n approaches infinity.

Links to other things:
Notes: Timing notes , on recurrance, all notes
Solutions: recurrance solutions, No Guess solution, No Guess solution to b, all assignments