Questions tagged [analysis-of-algorithms]

$ \def \c {c _ { \text {crit} }} $ The analysis of algorithms is the process of finding the computational complexity of algorithms - the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.

Often, especially in the case of divide-and-conquer algorithms, the function describing the performance of the algorithm can be described by a functional equation. The most famous one is the master equation $$ T ( n ) = a T \left( \frac n b \right) + f ( n ) \text . \tag {*} \label m $$ The master theorem asserts that under certain conditions, the growth rate of a function $ T $ satisfying \eqref{m} can be determined in terms of $ \c = \log _b a $ as follows:

1. If $ f ( n ) = O ( n ^ c ) $ for some $ c < \c $, then $ T ( n ) = \Theta ( n ^ { \c } ) $.
2. • If $ f ( n ) = \Theta \left( n ^ { \c } ( \log n ) ^ k \right) $ for some $ k > - 1 $, then $ T ( n ) = \Theta \left( n ^ { \c } ( \log n ) ^ { k + 1 } \right) $.
   • If $ f ( n ) = \Theta \left( \frac { n ^ { \c } } { \log n } \right) $, then $ T ( n ) = \Theta ( n ^ { \c } \log \log n ) $.
   • If $ f ( n ) = \Theta \left( n ^ { \c } ( \log n ) ^ k \right) $ for some $ k < - 1 $, then $ T ( n ) = \Theta ( n ^ { \c } ) $.
3. If $ f ( n ) = \Omega ( n ^ c ) $ for some $ c > \c $ and $ a f \left( \frac n b \right) \le k f ( n ) $ for some constant $ k < 1 $, then $ T ( n ) = \Theta \big( f ( n ) \big) $.

A generalization of the master theorem called the Akra-Bazzi theorem is used in case of divide-and-conquer algorithms which do not necessarily divide a problem into equally-sized sub-problems. The corresponding recurrence relation for that kind of algorithm is $$ T ( n ) = \sum _ { i = 1 } ^ k a _ i T \big( b _ i n + g _ i ( n ) \big) + f ( n ) \text . \tag {**} \label {ab} $$ Under certain conditions, including $ | f ( n ) | = O ( n ^ c ) $ for some constant $ c $ and $ | g _ i ( n ) | = O \left( \frac n { ( \log n ) ^ { 1 + \epsilon } } \right) $ for some positive constant $ \epsilon $, the growth rate of a function $ T $ satisfying \eqref{ab} can be expressed as $$ \Theta \Bigg( n ^ { \c } \left( 1 + \int _ 1 ^ n \frac { f ( x ) } { x ^ { \c + 1 } } \ \mathrm d x \right) \Bigg) \text , $$ where $ \c $ is the unique constant for which $ \sum _ { i = 1 } ^ k a _ i b _ i ^ { \c } = 1 $.

Sources:
Wikipedia pages on analysis of algorithms, the master theorem for divide-and-conquer recurrences and the Akra-Bazzi theorem
Leighton's note on the Akra-Bazzi theorem