sec recurrence relations the extra cost to join the two pieces together thusthe true cost must be somewhere between cn and let us now try ( < log for the base casethe definition of the recurrence sets ( <( log assume (induction hypothesisthat ( < log thent( ( < log < (log < log which is what we seek to prove in similar fashionwe can prove that (nis in ohm( log nthust(nis also th( log nexample we know that the factorial function grows exponentially how does it compare to to nn do they all grow "equally fast(in an asymptotic sense)we can begin by looking at few initial terms nn we can also look at these functions in terms of their recurrences = nn( ) = - ( > = - ( > at this pointour intuition should be telling us pretty clearly the relative growth rates of these three functions but how do we prove formally which grows the fastestand how do we decide if the differences are significant in an asymptotic senseor just constant factor differenceswe can use logarithms to help us get an idea about the relative growth rates of these functions clearlylog equally clearlylog nn log we can easily see from this that is (nn )that isnn grows asymptotically faster than