polynomial in n

T1 (n1)     =     t12 + T2(n2) + t21    <    p(n1) * T2 (n1)
n2 = poly (n1) (i.e., must be bounded by a polynomial in n1 - otherwise, t12 non polynomial)

Cases

  1. suppose n2 = 2n1

    then too much time would be needed to construct l1 -> l2     t12>    2n1

    So, t12 and t21 must be bounded by a polynomial in n1.

  2. Suppose T2(n) is an exponential function.
    further suppose that n2 = 2n1

      T2(n1)    =    2n1
      T2(n2)    =    2n2    =    22n1

      22n1    is not    <    poly(n) * 2n1

    must be related by at most a polynomial of n1
    T2(n2) is not    < poly(n1)   *   T2(n1)

  3. Suppose T2(n) = n2
    further suppose that n2 = 2n1

      T2(n2)    <    poly(n1)   *   T2(n1)
      T2(n2)     =    (n2)2     =     (2n1)2    =     4n12

      T2(n1)     =   n12 (by definition),
      so we are cool since we have T2(n2)    < poly(n1)   *   T2(n1) in the form of 4n12

If T2(n) is polynomial and n2 = poly(n1) then
T1(n1) <     t12 + T2(n2) + t21    <   t12 + t21 + poly(n1) * T2(n1)   < poly2 (n1) * T2(n1)

and hence T1(n1) is some poly. in n.