Asymptotic analysis - Revision history

Dhruvbird: Add a line explaining the non-equivalence of the limit based and Oh-based notation.

2012-10-10T02:12:25Z

Add a line explaining the non-equivalence of the limit based and Oh-based notation.

Brian at 08:48, 1 January 2012

2012-01-01T08:48:28Z

Brian: /* How to analyze an algorithm */

2012-01-01T06:28:38Z

‎How to analyze an algorithm

Brian: /* The master theorem */ : log -> \log

2012-01-01T06:27:49Z

‎The master theorem: : log -> \log

Brian: /* Recursive functions */

2012-01-01T06:19:54Z

‎Recursive functions

Brian: added citation

2011-12-29T09:30:11Z

added citation

Brian at 08:55, 28 December 2011

2011-12-28T08:55:52Z

Show changes

Brian: Created page with "In theoretical computer science, '''asymptotic analysis''' is the most frequently used technique to quantify the performance of an algorithm. Its name refers to the fact that..."

2011-12-25T07:13:57Z

Created page with "In theoretical computer science, '''asymptotic analysis''' is the most frequently used technique to quantify the performance of an algorithm. Its name refers to the fact that..."

New page

In theoretical computer science, '''asymptotic analysis''' is the most frequently used technique to quantify the performance of an [[algorithm]]. Its name refers to the fact that this form of analysis neglects the exact amount of time or memory that the algorithm uses on specific cases, but is concerned only with the algorithm's asymptotic behaviour—that is, how the algorithm performs in the limit of infinite problem size.

==Irrelevance of constant factor==
It does this by neglecting the so-called [[invisible constant factor]]. The reasoning is as follows. Suppose Alice and Bob each write a program to solve the same task. Whenever Alice's program and Bob's program are executed with the same input on a given machine (which we'll call ALOPEX), Alice's program is always about 25% faster than Bob's program. The table below shows the number of lines of input in the first column, the execution time of Alice's program in the second, and the execution time of Bob's program in the third:
{|
! N
! Alice
! Bob
|-
| 104
| 0.026
| 0.032
|-
| 105
| 0.36
| 0.45
|-
| 106
| 3.8
| 4.7
|}
Practically speaking, Alice's program is faster. In theory, however, the two programs have equally efficient algorithms. This is because an algorithm is an abstraction independent of the machine on which it runs, and we could make Bob's program just as fast as Alice's by running it on a computer that is 25% faster than the original one.

If this argument sounds unconvincing, consider the following argument. Programs, as they run on real machines, are built up from a series of very simple instructions, each of which is executed in a period of time on the order of a nanosecond on a typical microcomputer. However, some instructions happen to be faster than others.

Now, suppose we have the following information:
* On ALOPEX, the <code>MULTIPLY</code> instruction takes 1 nanosecond to run whereas the <code>DIVIDE</code> instruction takes 2 nanoseconds to run.
* We have another machine, which we'll call KITSUNE, on which these two instructions both take 1.5 nanoseconds to run.
* When Bob's program is given 150000 lines of input, it uses 1.0×108 multiplications and 3.0×108 divisions, whereas Alice's program uses 4.0×108 multiplications and 0.8×108 divisions on the same input.
Then we see that:
# On ALOPEX, Bob's program will require (1 ns)×(1.0×108) + (2 ns)×(3.0×108) = 0.70 s to complete all these instructions, whereas Alice's program will require (1 ns)×(4.0×108) + (2 ns)×(0.8×108) = 0.56 s; Alice's program is faster by 25%.
# On KITSUNE, Bob's program will require (1.5 ns)×(1.0×108) + (1.5 ns)×(3.0×108) = 0.60 s, whereas Alice's will require (1.5 ns)×(4.0×108) + (1.5 ns)×(0.8×108) = 0.72 s. Now Bob's program is 20% faster than Alice's.
Thus, we see that a program that is faster on one machine is not necessarily faster on another machine, so that comparing exact running times in order to decide which algorithm is faster is not meaningful.

The same can be said about memory usage. On a 32-bit machine, an <code>int</code> (integer data type in the C programming language) and an <code>int*</code> (a [[pointer]] to an <code>int</code>) each occupy 4 bytes of memory, whereas on a 64-bit machine, an <code>int</code> uses 4 bytes and an <code>int*</code> uses 8 bytes; so that an algorithm that uses more pointers than integers may use more memory on a 64-bit machine and less on a 32-bit machine when compared to a competing algorithm that uses more integers than pointers.

==Why the machine is now irrelevant==
The preceding section should convince you that if two programs's running times differ by at most a constant factor, then their algorithms should be considered equally efficient, as we can make one or the other faster in practice just by designing our machine accordingly. Let's now consider a case in which one algorithm can actually be faster than another.

Suppose that Alice and Bob are now given a new problem to solve and their algorithms perform as follows on ALOPEX:
{|
! N
! Alice
! Bob
|-
| 103
| 0.040
| 0.0013
|-
| 104
| 0.38
| 0.13
|-
| 105
| 3.7
| 12
|-
| 106
| 37
| 1500
|}
Observe that when we multiply the problem size by 10, Alice's program takes about 10 times longer, but Bob's program takes about 100 times longer. Thus, even though Bob's program is faster than Alice's program for small inputs (10000 lines or fewer), '''in the limit of infinite problem size''', Alice's program will ''always'' be faster. Even if we run Bob's program on a supercomputer and Alice's program on a 386, for sufficiently large input, Alice's program will always finish first, since no matter how much of a disadvantage Alice's program has, it catches up more and more as we increase the problem size; it ''scales better'' than Bob's algorithm.

Also observe that Alice's algorithm has running time approximately proportional to the size of its input, whereas Bob's algorithm has running time approximately proportional to the square of the size of its input. We write that Alice's algorithm has running time <math>\Theta(N)</math> whereas Bob's has running time <math>\Theta(N^2)</math>. Notice that we don't bother to write the constant factor, since this varies from machine to machine; we write only the part that tells us how the algorithm scales. Since <math>N^2</math> grows much more quickly than <math>N</math> as <math>N</math> increases, we see that Bob's algorithm is slower than Alice's.

==Notation==
We are now ready to give an explanation of the <math>\Theta</math>-notation used in the previous section. (See section [[#Big theta notation|Big theta notation]] below.) We suppose that functions <math>f</math> and <math>g</math> map the positive integers to the positive real numbers. The interpretation is that <math>f(n)</math> represents the amount of time (in some units) that it takes a certain algorithm to process an input of size <math>n</math> when run on a certain machine.

===Big O notation===
We say that <math>f(n) \in O(g(n))</math> when <math>g(n)</math> is asymptotically ''at least as large'' as <math>f(n)</math>. This is read ''f is big-O of g''. Mathematically, this is defined to mean that there are some constants <math>n_0, c</math> such that <math>c\cdot g(n) \geq f(n)</math> for all <math>n \geq n_0</math>; to read it idiomatically, ''for sufficiently large <math>n</math>, <math>f(n)</math> is bounded by a constant times <math>g(n)</math>.''

This means that if we plotted <math>f</math> and <math>g</math> on the same set of axes, with <math>n</math> along the positive x-axis, then we can scale the curve <math>g</math> such that it always lies above the curve <math>f</math>.

For example, if we plot <math>f(n) = 3n+1</math> and <math>g(n) = 2n+1</math> on the same set of axes, then we see that by scaling <math>g</math> by a factor of <math>\frac{3}{2}</math>, we can make the curve of <math>g</math> lie above the curve of <math>f</math>. Therefore, <math>3n+1 \in O(2n+1)</math>.

Similarly, if we plot <math>f(n) = 5n</math> and <math>g(n) = n^2</math> on the same set of axes, and we scale <math>g</math> by a factor of 5, we will make the curve of <math>g</math> lie above the curve of <math>f</math>. So <math>5n \in O(n^2)</math>.

On the other hand, if <math>f(n) = n^2</math> and <math>g(n) = 5n</math>, no matter how much we scale <math>g</math>, we cannot make it lie above <math>f</math>. We could for example try scaling <math>g</math> by a factor of 100. Then, we will have <math>f(n) \leq g(n)</math> for all <math>n</math> up to 500, but for <math>n > 500</math>, <math>f</math> will be larger. If we try scaling <math>g</math> by a factor of 1000, then <math>f</math> will still catch up at <math>n > 5000</math>, and so on. So <math>n^2 \notin O(5n)</math>.

Big O notation is the most frequently used notation for describing an algorithm's running time, since it provides an ''upper bound''. If, for example, we write that an algorithm's running time is <math>O(n^2)</math>, then this is a guarantee that, as <math>n</math> grows larger, the relative increase in the algorithm's running time is at most that of <math>n^2</math>, so that when we double <math>n</math>, our algorithm's running time will be at most quadrupled, and so on. This characterization is '''machine-independent'''; if an algorithm is <math>O(n^2)</math> on one machine then it will be <math>O(n^2)</math> on any other machine as well. (This holds true under the assumption that they are both classical von Neumann machines, which is the case for all computing machines on Earth right now.)

An algorithm that is <math>O(n^k)</math> for some constant <math>k</math> is said to be '''polynomial-time'''; its running time is bounded above by a polynomial in its input size. Polynomial-time algorithms are considered "efficient", because they provide the guarantee that as we double the problem size, the running time increases by a factor of at most <math>2^k</math>. If an algorithm is not polynomial-time, it could be that doubling the problem size from 1000 to 2000 increases the running time by a factor of 10, but doubling the problem size from 10000 to 20000 increases the running time by a factor of 100, and the factor becomes worse and worse as the problem size increases; these algorithms are considered inefficient. The first polynomial-time algorithm discovered that solves a particular problem is usually considered a breakthrough.

===Big omega notation===
Big omega notation is the opposite of big O notation. The statement that <math>f(n) \in O(g(n))</math> is equivalent to the statement that <math>g(n) \in \Omega(f(n))</math>. Conceptually, it means that <math>f(n)</math> is asymptotically at least as large as <math>g(n)</math>. Therefore, big omega notation provides a lower bound, instead of an upper bound. For example, if an algorithm's running time is <math>\Omega(k^n)</math> for some <math>k > 1</math>, then when we increase the problem size from <math>n</math> to <math>n+c</math>, the running time of our algorithm will increase by a factor of ''at least'' <math>k^c</math>. Approximately doubling the input size will then approximately ''square'' the running time. This scaling behaviour, called '''exponential time''', is considered extremely inefficient.

===Big theta notation===
If <math>f(n) \in O(g(n))</math> ''and'' <math>f(n) \in \Omega(g(n))</math>, then <math>f</math> and <math>g</math> differ by only a constant factor from each other, like the running time of Alice and Bob's algorithms from the first section. In this case, we write <math>f(n) \in \Theta(g(n))</math> or equivalently <math>g(n) \in \Theta(f(n))</math>. Whereas big O notation gives us an ''upper bound'' on a function, such as an algorithm's running time as a function of its input size, and big omega notation gives us a ''lower bound'', big theta notation gives us both simultaneously—it gives us an ''expectation'' of that function. This is often expressed as ''f is on the order of g''.

Thus, if an algorithm's running time is <math>\Theta(n^2)</math>, and we double the input size <math>n</math>, then we have an expectation that the running time of the algorithm will be nearly exactly four times what it was before, whereas big O notation would only tell us that it is not more than four times greater, and big omega notation that it is at least four times greater.

===Little O notation===
Whereas the big O notation <math>f(n) \in O(g(n))</math> expresses that <math>g</math> grows ''at least as quickly'' as <math>f</math> in an asymptotic, constant-factor-oblivious sense, little O notation, as in <math>f(n) \in o(g(n))</math>, expresses that <math>g</math> grows ''strictly more quickly'' than <math>f</math> in the limit of infinite <math>n</math>. It means that <math>\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0</math>. This notation is not used very often in computer science (simply because it is rarely useful).

===Little omega notation===
Little omega notation is the opposite of little O notation; the statement that <math>f(n) \in o(g(n))</math> is equivalent to the statement that <math>g(n) \in \omega(f(n))</math>. Little omega notation, like little O notation, is rarely used in computer science.

===Tilde/swung dash===
The notation <math>f(n) \sim g(n)</math> means that <math>\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1</math>. This is usually not used when discussing running times of algorithms, because it does ''not'' ignore the constant factor the way that the other notations do; hence <math>n \in \Theta(2n)</math> but <math>n \nsim 2n</math>. On the other hand, <math>n \sim n+1</math>. However, this notation may be useful when we care about the constant factor because we are quantifying something that depends on only the algorithm itself instead of the machine it runs on. For example, the amount of time an algorithm uses to sort its input depends on what machine it runs on, but the number of comparisons that the algorithm uses for a given input does not depend on the machine. In this case we might say that one algorithm requires <math>\sim N \log_2 N</math> comparisons, whereas another requires <math>\sim 2 N \log_2 N</math> comparisons. Both algorithms are <math>\Theta(N \log N)</math>, but the tilde notation distinguishes their performance.

[[Category:Pages needing diagrams]]

← Older revision		Revision as of 08:48, 1 January 2012
Line 312:		Line 312:
	<references/>		<references/>
	[[Category:Pages needing diagrams]]		[[Category:Pages needing diagrams]]
		+	[[Category:Incomplete]]

@@ Line 289: / Line 289: @@
 We would like to have some way to tackle the general case, without so much messy mathematical reasoning in each individual case. By ''general case'', we mean that we assume that to solve an instance of size <math>n</math> using some algorithm, we divide it into chunks of size about <math>\frac{n}{b}</math>, and solve <math>a</math> subproblems using those chunks, along with extra work in the amount of <math>f(n)</math>, unless <math>n < c</math> for some constant <math>c</math>, which represents a base case that can be solved in <math>O(1)</math> time. For example, in the first of the three examples above, we have <math>a = 2, b = 2, f(n) = n</math>; in the second, <math>a = 3, b = 2, f(n) = n</math>, and in the third, <math>a = 2, b = 2, f(n) = n \log n</math>.
-===The master theorem===
+====The master theorem====
 The authoritative statement of the '''master theorem''' is from CLRS<ref name="CLRS">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.</ref>. Suppose that <math>a \geq 1</math> and <math>b > 1</math> above, and <math>f</math> is positive. Then, there are three cases:
 # If <math>f(n) \in O(n^{\log_b a - \epsilon})</math> for some <math>\epsilon > 0</math>, then the overall running time is <math>\Theta(n^{\log_b a})</math>.
@@ Line 303: / Line 303: @@
 An actual proof of the master theorem is given in CLRS.
-===Akra&ndash;Bazzi theorem===
+====Akra&ndash;Bazzi theorem====
 TODO

@@ Line 292: / Line 292: @@
 The authoritative statement of the '''master theorem''' is from CLRS<ref name="CLRS">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.</ref>. Suppose that <math>a \geq 1</math> and <math>b > 1</math> above, and <math>f</math> is positive. Then, there are three cases:
 # If <math>f(n) \in O(n^{\log_b a - \epsilon})</math> for some <math>\epsilon > 0</math>, then the overall running time is <math>\Theta(n^{\log_b a})</math>.
-# If <math>f(n) \in \Theta(n^{\log_b a} log^k n)</math>, for some <math>k \geq 0</math>, then the overall running time is <math>\Theta(n^{\log_b a} log^{k+1} n)</math>.
+# If <math>f(n) \in \Theta(n^{\log_b a} \log^k n)</math>, for some <math>k \geq 0</math>, then the overall running time is <math>\Theta(n^{\log_b a} log^{k+1} n)</math>.
 # If <math>f(n) \in \Omega(n^{\log_b a + \epsilon})</math> for some <math>\epsilon > 0</math>, and, furthermore, <math>af\left(\frac{n}{b}\right) \leq cf(n)</math> for some <math>c < 1</math> and all sufficiently large <math>n</math>, then the overall running time is <math>\Theta(f(n))</math>.
 For example, Karatsuba multiplication falls into the first case, since <math>f(n) = n</math> and <math>\log_2 3 \approx 1.58</math>. The theorem then tells us that the overall running time is <math>O(n^{\log_2 3})</math>. What is happening here is that as we proceed from one level to the next, the amount of work done on the current level increases exponentially or faster. In this particular case, each level entails 1.5 times as much work as the previous level. Intuitively, this means most of the work is done on the lowest level, on which we have <math>n</math> subproblems, each with size 1. The earlier analysis then applies. The reason why we need <math>f(n) \in O(n^{\log_b a - \epsilon})</math> is precisely to ensure this exponential growth. If <math>f(n)</math> is exactly <math>n^{\log_b a}</math>, then we will have <math>af\left(\frac{n}{b}\right) = a\frac{n^{\log_b a}}{b^{\log_b a}} = n^{\log_b a} = f(n)</math>, that is, the amount of work done on each level will be the same. But if <math>f(n)</math> grows more slowly than this, then <math>f(n)</math> will be less than <math>af\left(\frac{n}{b}\right)</math>. If it grows polynomially more slowly (that is, by a factor of <math>n^\epsilon</math> or more), then the desired exponential growth will be attained.
-Merge sort and the closest pair of points algorithm are covered by case 2. For merge sort, we have <math>k = 0</math> (there is no log factor at all). Here the time spent on each level is the same, since <math>f(n) = af\left(\frac{n}{b}\right)</math> if <math>f(n) = n^{log_b a}</math>, so we simply multiply <math>f(n)</math> by the number of levels, that is, <math>\log_b n \in \Theta(\log n)</math>. For the closest pair of points algorithm, we have <math>k = 1</math>. When <math>k > 0</math>, then there is a decrease in the amount of work done as we go further down, but it is slower than an exponential decay. In each case the average amount of work done per level is on the order of the amount of work done on the topmost level, so in each case we obtain <math>\Theta(f(n) \log n)</math> time.
+Merge sort and the closest pair of points algorithm are covered by case 2. For merge sort, we have <math>k = 0</math> (there is no log factor at all). Here the time spent on each level is the same, since <math>f(n) = af\left(\frac{n}{b}\right)</math> if <math>f(n) = n^{\log_b a}</math>, so we simply multiply <math>f(n)</math> by the number of levels, that is, <math>\log_b n \in \Theta(\log n)</math>. For the closest pair of points algorithm, we have <math>k = 1</math>. When <math>k > 0</math>, then there is a decrease in the amount of work done as we go further down, but it is slower than an exponential decay. In each case the average amount of work done per level is on the order of the amount of work done on the topmost level, so in each case we obtain <math>\Theta(f(n) \log n)</math> time.
 Case 3 is not often encountered in practice. When <math>f(n) \geq \frac{1}{c}af\left(\frac{n}{b}\right)</math> (with <math>\frac{1}{c} > 1</math>), there is an exponential (or faster) decay as we proceed from the top to the lower levels, so most of the work is done at the top, and hence the <math>\Theta(f(n))</math> behaviour is obtained. The condition that <math>f(n) \in \Omega(n^{\log_b a + \epsilon})</math> is not actually needed in the statement of Case 3, since it is implied by the condition that <math>af\left(\frac{n}{b}\right) \leq cf(n)</math>. The reason why the theorem is stated as it is above is that if <math>f(n)</math> is actually of the form <math>cn^{\log_b a + \epsilon}\log^k n</math>, which covers most of the cases, then the other condition is implied, and we don't need to explicitly check it, but can instead just look at the form of <math>f(n)</math>. However, there are some possibilities for <math>f(n)</math> that are not "well-behaved", and will not satisfy the condition <math>af\left(\frac{n}{b}\right) \leq cf(n)</math>.

← Older revision		Revision as of 06:19, 1 January 2012
Line 276:		Line 276:

	===Recursive functions===		===Recursive functions===
		+	Many algorithms work by breaking the input down into smaller pieces, [[recursively]] solving each smaller piece as though it were an independent problem, and then combining the results to obtain a solution to the original instance. This algorithmic paradigm is known as ''divide and conquer'', and its running time is usually analyzed slightly differently from that of the simpler algorithms from the previous section.
		+
		+	Examples:
		+	* [[Merge sort]], which sorts a list by dividing it into two sub-lists, sorting each sub-list, and then merging the two sorted sub-lists to obtain the original list, sorted. The merge step takes <math>O(n)</math> time if the original list had <math>n</math> elements. The overall running time is <math>O(n \log n)</math>.
		+	* [[Karatsuba multiplication]], which multiplies two <math>n</math>-digit numbers (see [[Big numbers]]) by dividing each number into two halves and recursively multiplying three pairs of halves, along with some additions and subtractions which take <math>O(n)</math> time in total. The overall running time is <math>O(n^{\log_2 3})</math>.
		+	* One solution to the [[closest pair of points]] problem finds the closest pair by dividing the point set with a half plane to obtain two sets of points of approximately half the size, finding the closest pair of points within each set, and then sorting points close to the dividing line and sweeping to find the closest pair across the division, which takes <math>O(n \log n)</math> time (for the sorting). The overall running time is then <math>O(n \log^2 n)</math>. (NB: This can be improved to <math>O(n \log n)</math> if we concomitantly run merge sort, rather than re-sorting along the dividing line in each step.)
		+
		+	How do we analyze the running time of such algorithms? We can reason as follows:
		+	* In the case of merge sort, we start out with one instance (the original list of size <math>n</math>), which gives rise to two subinstances of size <math>n/2</math>; these in turn give rise to a total of four subinstances of size <math>n/4</math>, and so on down to subinstances of size 1 or 2. There are about <math>\log_2 n</math> "levels" to this scheme, and at each level, we have about <math>2^k</math> subinstances of size <math>n/2^k</math>, and a linear amount of work is required in the "conquer" step of each; so that is about <math>cn</math> steps at each level, or about <math>cn \log n</math> steps in total, giving <math>O(n \log n)</math>.
		+	* In Karatsuba multiplication, there will again be about <math>\log_2 n</math> levels. On the topmost level, we have one instance with size <math>n</math>. On the next level, we have three instances with size <math>n/2</math>, and then nine instances with size <math>n/4</math>, and so on down. A linear amount of additional work is required for the "conquer" step for each instance, so that is about <math>cn</math> work on the topmost level, about <math>\frac{3}{2}cn</math> on the next level, and so on down. So the total running time will be about <math>cn \sum_{k=0}^{\log_2 n} \left(\frac{3}{2}\right)^k = cn\left(\frac{\frac{3}{2}^{k+1}-1}{\frac{3}{2}-1}\right) = O\left(n\left(\frac{3}{2}\right)^{\log_2 n}\right) = O(n^{\log_2 3})</math>. (Several steps were omitted.)
		+	* In the third algorithm listed above, there are again about <math>\log_2 n</math> levels; on the topmost level, the work done is <math>cn \log n</math>; then <math>2c\left(\frac{n}{2}\log\left(\frac{n}{2}\right)\right)</math> on the next level, since we will have two subinstances of size <math>\frac{n}{2}</math>, which will each require <math>O\left(\frac{n}{2}\log\left(\frac{n}{2}\right)\right)</math> work; then on the next level, <math>4c\left(\frac{n}{4}\log\left(\frac{n}{4}\right)\right)</math>, and so on down; the total work done is about <math>O\left(\sum_{k=0}^{\log_2 n} 2^k \frac{n}{2^k}\log\left(\frac{n}{2^k}\right)\right) = n\cdot O\left(\sum_{k=0}^{\log_2 n}\log\left(\frac{n}{2^k}\right)\right)</math>. This gives us an arithmetic series, with first term <math>\log n</math> (here <math>k = 0</math>) and last term about 0 (for when <math>\frac{n}{2^k} \approx \frac{n}{n} = 1</math> since <math>k \approx \log_2 n</math>) and a total of about <math>\log_2 n</math> terms; its sum is then about <math>\log n \log_2 n</math> giving <math>O(n \log^2 n)</math> overall.
		+	We would like to have some way to tackle the general case, without so much messy mathematical reasoning in each individual case. By ''general case'', we mean that we assume that to solve an instance of size <math>n</math> using some algorithm, we divide it into chunks of size about <math>\frac{n}{b}</math>, and solve <math>a</math> subproblems using those chunks, along with extra work in the amount of <math>f(n)</math>, unless <math>n < c</math> for some constant <math>c</math>, which represents a base case that can be solved in <math>O(1)</math> time. For example, in the first of the three examples above, we have <math>a = 2, b = 2, f(n) = n</math>; in the second, <math>a = 3, b = 2, f(n) = n</math>, and in the third, <math>a = 2, b = 2, f(n) = n \log n</math>.
		+
		+	===The master theorem===
		+	The authoritative statement of the '''master theorem''' is from CLRS<ref name="CLRS">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.</ref>. Suppose that <math>a \geq 1</math> and <math>b > 1</math> above, and <math>f</math> is positive. Then, there are three cases:
		+	# If <math>f(n) \in O(n^{\log_b a - \epsilon})</math> for some <math>\epsilon > 0</math>, then the overall running time is <math>\Theta(n^{\log_b a})</math>.
		+	# If <math>f(n) \in \Theta(n^{\log_b a} log^k n)</math>, for some <math>k \geq 0</math>, then the overall running time is <math>\Theta(n^{\log_b a} log^{k+1} n)</math>.
		+	# If <math>f(n) \in \Omega(n^{\log_b a + \epsilon})</math> for some <math>\epsilon > 0</math>, and, furthermore, <math>af\left(\frac{n}{b}\right) \leq cf(n)</math> for some <math>c < 1</math> and all sufficiently large <math>n</math>, then the overall running time is <math>\Theta(f(n))</math>.
		+
		+	For example, Karatsuba multiplication falls into the first case, since <math>f(n) = n</math> and <math>\log_2 3 \approx 1.58</math>. The theorem then tells us that the overall running time is <math>O(n^{\log_2 3})</math>. What is happening here is that as we proceed from one level to the next, the amount of work done on the current level increases exponentially or faster. In this particular case, each level entails 1.5 times as much work as the previous level. Intuitively, this means most of the work is done on the lowest level, on which we have <math>n</math> subproblems, each with size 1. The earlier analysis then applies. The reason why we need <math>f(n) \in O(n^{\log_b a - \epsilon})</math> is precisely to ensure this exponential growth. If <math>f(n)</math> is exactly <math>n^{\log_b a}</math>, then we will have <math>af\left(\frac{n}{b}\right) = a\frac{n^{\log_b a}}{b^{\log_b a}} = n^{\log_b a} = f(n)</math>, that is, the amount of work done on each level will be the same. But if <math>f(n)</math> grows more slowly than this, then <math>f(n)</math> will be less than <math>af\left(\frac{n}{b}\right)</math>. If it grows polynomially more slowly (that is, by a factor of <math>n^\epsilon</math> or more), then the desired exponential growth will be attained.
		+
		+	Merge sort and the closest pair of points algorithm are covered by case 2. For merge sort, we have <math>k = 0</math> (there is no log factor at all). Here the time spent on each level is the same, since <math>f(n) = af\left(\frac{n}{b}\right)</math> if <math>f(n) = n^{log_b a}</math>, so we simply multiply <math>f(n)</math> by the number of levels, that is, <math>\log_b n \in \Theta(\log n)</math>. For the closest pair of points algorithm, we have <math>k = 1</math>. When <math>k > 0</math>, then there is a decrease in the amount of work done as we go further down, but it is slower than an exponential decay. In each case the average amount of work done per level is on the order of the amount of work done on the topmost level, so in each case we obtain <math>\Theta(f(n) \log n)</math> time.
		+
		+	Case 3 is not often encountered in practice. When <math>f(n) \geq \frac{1}{c}af\left(\frac{n}{b}\right)</math> (with <math>\frac{1}{c} > 1</math>), there is an exponential (or faster) decay as we proceed from the top to the lower levels, so most of the work is done at the top, and hence the <math>\Theta(f(n))</math> behaviour is obtained. The condition that <math>f(n) \in \Omega(n^{\log_b a + \epsilon})</math> is not actually needed in the statement of Case 3, since it is implied by the condition that <math>af\left(\frac{n}{b}\right) \leq cf(n)</math>. The reason why the theorem is stated as it is above is that if <math>f(n)</math> is actually of the form <math>cn^{\log_b a + \epsilon}\log^k n</math>, which covers most of the cases, then the other condition is implied, and we don't need to explicitly check it, but can instead just look at the form of <math>f(n)</math>. However, there are some possibilities for <math>f(n)</math> that are not "well-behaved", and will not satisfy the condition <math>af\left(\frac{n}{b}\right) \leq cf(n)</math>.
		+
		+	An actual proof of the master theorem is given in CLRS.
		+
		+	===Akra–Bazzi theorem===
	TODO		TODO

@@ Line 227: / Line 227: @@
 * A cubic-time algorithm will suffice for <math>n</math> up to about 300.
 * A quadratic-time algorithm will suffice for <math>n</math> up to about 5000.
-* An <math>O(n \log n)</math> time algorithm will suffice for <math>n</math> up to about 200000. The number 100000 is a very common bound on input size in olympiad problems, and almost always suggests that a contestant should aim to invent an algorithm with time complexity of around <math>O(n \log n)</math>. (This aspect of olympiad contests has been criticized.) <math>O(n^2)</math> is almost always too slow in this case.
+* An <math>O(n \log n)</math> time algorithm will suffice for <math>n</math> up to about 200000. The number 100000 is a very common bound on input size in olympiad problems, and almost always suggests that a contestant should aim to invent an algorithm with time complexity of around <math>O(n \log n)</math>. (This aspect of olympiad contests has been criticized.)<ref>Ribiero, P. and Guerreiro, P. ''Improving the Automatic Evaluation of Problem Solutions in Programming Contests''. Olympiads in Informatics, 2009, Vol. 3, 132–143. Retrieved from http://www.mii.lt/olympiads_in_informatics/pdf/INFOL048.pdf</ref> <math>O(n^2)</math> is almost always too slow in this case.
 * A linear-time algorithm is typically required if the input can be even larger than this, usually 300000 or more lines.
@@ Line 280: / Line 280: @@
 ===Amortized analysis===
 TODO
 [[Category:Pages needing diagrams]]

@@ Line 101: / Line 101: @@
 ===Little O notation===
-Whereas the big O notation <math>f(n) \in O(g(n))</math> expresses that <math>g</math> grows ''at least as quickly'' as <math>f</math> in an asymptotic, constant-factor-oblivious sense, little O notation, as in <math>f(n) \in o(g(n))</math>, expresses that <math>g</math> grows ''strictly more quickly'' than <math>f</math> in the limit of infinite <math>n</math>. It means that <math>\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0</math>. This notation is not used very often in computer science (simply because it is rarely useful).
+Whereas the big O notation <math>f(n) \in O(g(n))</math> expresses that <math>g</math> grows ''at least as quickly'' as <math>f</math> in an asymptotic, constant-factor-oblivious sense, little O notation, as in <math>f(n) \in o(g(n))</math>, expresses that <math>g</math> grows ''strictly more quickly'' than <math>f</math> in the limit of infinite <math>n</math>. It means that <math>\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0</math>. This notation is not used very often in computer science (simply because it is rarely useful). Additionally, the limit based notation is not entirely equivalent to the big/little-Oh notation since the limit of the quotient might not exist in case of non-continuous functions such as the step function, etc...
 ===Little omega notation===