Summary of Algo Analysis / Slide 1 Algorithm complexity Problems algorithms programs Bounds are for the algorithms, rather than programs Algorithms are often written in pseudo-codes programs are just implementations of an algorithm, and almost always the details of the program do not affect the bounds We use almost something like C++. Bounds are for algorithms, rather than problems A problem can be solved with several algorithms, some are more efficient than others
Summary of Algo Analysis / Slide 2 Worst- / average- / best-case Worst-case running time of an algorithm The longest running time for any input of size n An upper bound on the running time for any input guarantee that the algorithm will never take longer Example: Sort a set of numbers in increasing order; and the data is in decreasing order The worst case can occur fairly often Best-case running time E.g. in searching a database for a particular piece of information
sort a set of numbers in increasing order; and the data is already in increasing order Average-case running time May be difficult to define what average means Summary of Algo Analysis / Slide 3 Asymptotic notations Upper bound O(g(N) Lower bound (g(N)) Tight bound (g(N)) Summary of Algo Analysis / Slide 4 Upper bound O(g(N) can be arbitrarily high Lower bound (g(N)) can be arbitrarily low
Most of estimations, often written as O(*), are tight bound (*) We dont write (*) because for many algorithms, we dont know the lower bound, so theoretically its not yet the tight bound (*), but the best or the lowest upper bound O(*) so far To get the tight bound, we need to estimate the lower bound Summary of Algo Analysis / Slide 5 Lower bound, usually harder than upper bound to prove, informally, find one input example
(of course, we may find an easier one, but we need to come up with a sufficiently difficult one to accommodate our estimator), that input has to do at least an amount of work that amount is lower bound a Consider a sequence of 0, 1, 2, , N-1, and search for 0 At least log N steps if N = 2^k An input of size n must take at least log N steps So the lower bound is Omega(log N) So the bound is tight, Theta(log N)
Summary of Algo Analysis / Slide 6 Solving the recurrence for binary search: N ) 1 2 N T ( ) 2 4 N T ( ) 3 8 T ( N ) T ( T ( N )k 2k
With 2k = N (or asymptotically), k=log N, we have T ( N ) k log N Thus, the running time is O(log N) Summary of Algo Analysis / Slide 7 Recurrence for Divide and Conquer with linear: T (1) 1 N T ( N ) 2 T ( ) N 2 2 T(N/2): two subproblems, each of size N/2 N: for patching two solutions to find solution to whole problem Summary of Algo Analysis / Slide 8 N )N
2 N 4 T ( ) 2 N 4 N 8 T ( ) 3 N 8 N 2 k T ( k ) kN 2 T ( N ) 2 T ( With 2k = N (or asymptotically), k=log N, we have T ( N ) N T (1) N log N N log N N Thus, the running time is O(N log N)