lec2.pdf

September 12, 2005 Copyright ? 2001-5 Erik D. De maine and Charles E. Leiserson Introduction to Algorithms L ECTURE 2 Asymptotic Notation ? O -, ?-, and Θ-notation Recurrences ? Substitution method ? Iterating the recurrence ? Recursion tree ? Master method Prof. Erik Demaine September 12, 2005 Copyright ? 2001-5 Erik D. De maine and Charles E. Leiserson Asymptotic notation O -notation (upper bounds): We write f ( n ) = O ( g ( n )) if there exist constants c > 0, n 0 > 0 s uch that 0 ≤ f ( n ) ≤ cg ( n ) f or all n ≥ n 0 . We write f ( n ) = O ( g ( n )) if there exist constants c > 0 , n 0 > 0 such that 0 ≤ f ( n ) ≤ cg ( n ) for all n ≥ n 0 . September 12, 2005 Copyright ? 2001-5 Erik D. De maine and Charles E. Leiserson Asymptotic notation O -notation (upper bounds): We write f ( n ) = O ( g ( n )) if there exist constants c > 0, n 0 > 0 s uch that 0 ≤ f ( n ) ≤ cg ( n ) f or all n ≥ n 0 . We write f ( n ) = O ( g ( n )) if there exist constants c > 0 , n 0 > 0 such that 0 ≤ f ( n ) ≤ cg ( n ) for all n ≥ n 0 . E XAMPLE : 2 n 2 = O ( n 3 ) ( c = 1 , n 0 = 2 ) September 12, 2005 Copyright ? 2001-5 Erik D. De maine and Charles E. Leiserson Asymptotic notation O -notation (upper bounds): We write f ( n ) = O ( g ( n )) if there exist constants c > 0, n 0 > 0 s uch that 0 ≤ f ( n ) ≤ cg ( n ) f or all n ≥ n 0 . We write f ( n ) = O ( g ( n )) if there exist constants c > 0 , n 0 > 0 such that 0 ≤ f ( n ) ≤ cg ( n ) for all n ≥ n 0 . E XAMPLE : 2 n 2 = O ( n 3 ) ( c = 1 , n 0 = 2 ) functions, not values September 12, 2005 Copyright ? 2001-5 Erik D. De maine and Charles E. Leiserson Asymptotic notation O -notation (upper bounds): We write f ( n ) = O ( g ( n )) if there exist constants c > 0, n 0 > 0 s uch that 0 ≤ f ( n ) ≤ cg ( n ) f or all n ≥ n 0 . We write f ( n ) = O ( g ( n )) if there exist constants c > 0 , n 0 > 0 such that 0 ≤ f ( n ) ≤