* Efficient procedures for solving large scale problems. Scalability. * Scalability * Classic data structures * Algorithmic Thinking * Sorting & trees A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them. Hard problems: There are some problems, however, for which no efficient solution is known. These are known as NP-complete problems. NP-complete problems are interesting because an efficient algorithm hasn't been found and nobody has proven that an efficient algorithm cannot exist. Np-complete is like god. Nobody knows if an efficient solutions exists or not. Also, if an efficient algorithm can be found for one NP-complete problem then an efficient algorithm must exist for all of them. If you can show that a problem is NP-complete, you can instead spend your time developing an efficient algorithm that gives a good, but not the best possible, solution. The "traveling-salesman problem" is an NP-complete problem. So any solution is good enough because an efficient solution has not been found yet. In order to elicit the best performance from multicore computers, we need to design algorithms with parallelism in mind. Multithreaded algorithms exist to take advantage of multiple cores. Championship chess programs use this. 1.1-1: Give a real-world example that requires sorting or a real-world example that requires computing a convex hull. Names in an address book. 1.1-2: Other than speed, what other measures of efficiency might one use in a real-world setting? The amount of space required. 1.1-3: Select a data structure that you have seen previously, and discuss its strengths and limitations. Balanced binary search trees are excellent for finding data quickly but a bit complicated when it comes to trying to keep it balanced efficiently. 1.1-4: How are the shortest-path and traveling-salesman problems given above similar? How are they different? The shortest path problem is looking for an efficient solution that routes from point A to point B. The traveling-salesman problem is similar except that the sales person needs to visit multiple locations then return to the starting point in the most efficient way. These problems are similar because the shortest path from point A to B can be used to help determine a good enough solution for the traveling-salesman problem. Both of these problems are considered an NP-complete problems because it hasn't been proven if an efficient algorithm can or cannot exist. 1.1-5: Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately" the best is good enough. * Traveling to Mars. Humans have a finite amount of time to live so choosing a point in time to travel that doesn't align with orbital conditions might make it impossible for humans to survie the trip. * Driving directions from point A to B. # Efficiency Different algorithms devised to solve the same problem often differ dramatically in their efficiency. * insertion sort takes n time to sort n items. * merge sort takes time roughly equal to nlg(n) time to sort n items. By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runes more than 17 times faster than computer A! As the problem size increases, so does the relative advantage of merge sort. 1.2-1: Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved. A fuzzy finder like `fzf`. This type of program needs to perform string similarity analysis over any input provided and provide results as the person types letters to reduce the total size of eligible results. 1.2-2: Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size `n`, insertion sort runs in `8n^2` steps, while merge sort runs in `64nlg(n)` steps. For which values of `n` does insertion sort beat merge sort? The following program produces a result of '44'. ```golang func main() { fmt.Println("n,isort,msort") for n := 2.0; n < 1000.0; n++ { isort := 8 * math.Pow(n, 2) msort := 64 * (n * math.Log2(n)) fmt.Printf("%v,%v,%v\n", n, isort, msort) if isort > msort { break } } } ``` ``csv n,isort,msort 2,32,128 3,72,304.312800138462 4,128,512 5,200,743.0169903639559 6,288,992.6256002769239 7,392,1257.6950050818066 8,512,1536 9,648,1825.876800830772 10,800,2126.033980727912 11,968,2435.439859520657 12,1152,2753.251200553848 13,1352,3078.7658454933885 14,1568,3411.390010163613 15,1800,3750.614971784178 16,2048,4096 17,2312,4447.159571280369 18,2592,4803.753601661543 19,2888,5165.4798563474 20,3200,5532.067961455824 21,3528,5903.274616214654 22,3872,6278.879719041314 23,4232,6658.683199315923 24,4608,7042.502401107696 25,5000,7430.169903639559 26,5408,7821.531690986777 27,5832,8216.445603738473 28,6272,8614.780020327225 29,6728,9016.412726956773 30,7200,9421.229943568356 31,7688,9829.12547980756 32,8192,10240 33,8712,10653.760380085054 34,9248,11070.319142560738 35,9800,11489.593957956724 36,10368,11911.507203323086 37,10952,12335.985569809354 38,11552,12762.9597126948 39,12168,13192.363938280172 40,12800,13624.135922911648 41,13448,14058.216460117852 42,14112,14494.549232429308 43,14792,14933.080604940173 44,15488,15373.759438082629 ``` 1.2-3: What is the smallest value of `n` such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine? 15. Calculated using: ```golang func main() { fmt.Println("n,100n^2,2^n") for n := 1.0; n < 100; n++ { x := 100 * math.Pow(n, 2) y := math.Pow(2, n) fmt.Printf("%v,%v,%v\n", n, x, y) if x < y { break } } } ``` ```csv n,100n^2,2^n 1,100,2 2,400,4 3,900,8 4,1600,16 5,2500,32 6,3600,64 7,4900,128 8,6400,256 9,8100,512 10,10000,1024 11,12100,2048 12,14400,4096 13,16900,8192 14,19600,16384 15,22500,32768 ``` Problem 1-1: Comparison of running times For each function `f(n)` and time `t` in the following table, determine the largest size `n` of a problem that can be solved in time `t`, assuming that the algorithm to solve the problem takes `f(n)` microseconds. 1 second = 1,000,000 microseconds 1 minute = 60 seconds = 60,000,000 microseconds 1 hour = 60 minutes = 3600 seconds = 3,600,000,000 microseconds 1 day = 24 hours = 1440 mins = 86400 seconds = 86,400,000,000 microseconds ```plaintext | | 1 second | 1 minute | 1 hour | 1 day | | lg n | 2^(10^6) | 2^(60*10^6) | 2^(3600*10^6) | 2^(86400*10^6) | | sqrt(n) | | | | | | n | 10^6 | 60*10^6 | 3600*10^6 | 86400*10^6 | | nlg(n) | | | | | | n^2 | | | | | | n^3 | | | | | | 2^n | | | | | | n! | | | | | ``` # Chapter 2 Getting Started 2.1 Insertion Sort Solves the sorting problem. Input: A sequence of `n` numbers `{a1,a2,...,aN}` Output: A permutation (reordering) of the input sequence such that: `{a1 <= a2 <= ... <= aN}` The numbers that we want to sort are known as keys. e.g. ```plaintext a. [5, 2, 4, 6, 1, 3] x i b. [2, 5, 4, 6, 1, 3] x x i c. [2, 4, 5, 6, 1, 3] x x x i d. [2, 4, 5, 6, 1, 3] x x x x i e. [1, 2, 4, 5, 6, 3] x x x x x i f. [1, 2, 3, 4, 5, 6] ``` ```plaintext A = {5,2,4,6,1,3} for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key ``` Loop invariants: * initializtion: it is true prior to the first iteration of the loop. * maintenance: if it is true before an iteration of the loop, it remains true before the next iteration. * termination: when the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct. Similar to mathematical induction, where to prove that a property holds, you prove a base case and an inductive step. Pseudocode conventions: * Indentation indicates block structure * Looping constructs `while`, `for`, and `repeat-until` and `if-else` conditional construct have interpretations similar to those in C. * compound data is organized into objects which are composed of attributes. 2.1-1: Illustrate the operation of INSERTION-SORT on the array `A = {31,41,59,26,41,58}` ```plaintext a. [31, 41, 59, 26, 41, 58] x i b. [31, 41, 59, 26, 41, 58] x x i c. [31, 41, 59, 26, 41, 58] x x x i d. [26, 31, 41, 59, 41, 58] x x x x i e. [26, 31, 41, 41, 59, 58] x x x x x i e. [26, 31, 41, 41, 58, 59] x x x x x x ``` 2.1-2: Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order. * non-increasing: descending * non-decreasing: ascending ```plaintext for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] < key A[i+1] = A[i] i = i - 1 A[i+1] = key ``` 2.1-3: Consider the **searching problem:** Input: A sequence of `n` numbers `A = {a1,a2,...,aN}` and a value `v`. Output: An index `i` such that `v = A[i]` or the special value `NIL` if `v` does not appear in `A`. Write pseudocode for `linear search`, which scans through the sequence, looking for `v`. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties. ```plaintext i = 0 for i < A.length and v != A[i] i = i + 1 if i >= A.length return NIL return i ``` * initialization: initialize `i` to first index of first element * maintenance: continue looping if `i` is less than size of `A` and `A[i]` is not equal to the target value `v`. * termination: terminate loop when the key matches the target value. 2.1-4: Consider the problem of adding two `n-bit` binary integers, stored in two `n-element` arrays `A` and `B`. The sum of the two integers should be stored in binary form in an `(n + 1)-element` array `C`. State the problem formally and write pseudocode for adding two integers. Input: Two sequences of `n` numbers `A = {a1,a2,...aN}` and `B = {b1,b2,...,bN}` Output: A sequence `C` with `n+1` numbers such that `C = {a1+b1,a2+b2,...,aN+bN}` ```plaintext i = 0 max = 2 ** A.length for i < A.length C[i] = A[i] + B[i] ``` ## 2.2 Analyzing Algorithms Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. * memory * communication bandwith * computer hardware Assume a generic one-processor, **random-access machine (RAM)** model of computation as our implementation. In the RAM model, instructions are executed one after another, with no concurrent operations. Analysis of insertion sort The time taken by INSERTION-SORT procedure depends on the input; sortin 1k numbers takes longer than 3 numbers. In general the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so we need to define "running time" and "size of input" more carefully. * input size: `n` * running time: number of steps executed. One line may take a different amount of time than another line, but we shall assume that each execution of `i`th line takes time c`i`, where c`i` is a constant. ```plaintext INSERTION-SORT(A) | cost | times | ===================================|======|==========| for j = 2 to A.length | c1 | n | key = A[j] | c2 | n-1 | i = j - 1 | c3 | n-1 | | |----------| | | n | while i > 0 and A[i] > key | c4 | Σ tj | | | j=2 | | |----------| | | n | A[i + 1] = A[i] | c5 | Σ (tj-1) | | | j=2 | | |----------| | | n i = i - 1 | c6 | Σ (tj-1) | | | j=2 | | |----------| A[i+1] = key | c7 | n -1 | ===================================|======|==========| ``` The running time is the s um of the running times for each statement executed; a statement that takes `cᵢ` steps to execute and executes `n` times will contribute `cᵢn` to the total running time. To compute `T(n)`, the running time of INSERTION-SORT on an input of `n` values, we sum the sum products of the **cost** and **times** columns. ```plaintext n n n T(n) = c1n + c2(n-1) + c4(n-1) + c4 Σ tj + c5 Σ (tj - 1) + c6 Σ (tj - 1) + c7(n-1) j=2 j=2 j=2 ``` Reasons for finding worst case running time. * upper bound on the running time for any input. * worst case occurs fairly often. * average case is roughly as bad as the worst case. Order of growth We consider only the leading term of a formula since the lower-order terms are relatively insignificant for large values of `n`. We also ignore the leading term's constant coefficient, since constant factors are less significant than the rate of growth in determining computational efficiency for large inputs. "theta of n-squared" 2.2-1: Express the function n^3 / 1000n^2 - 100n + 3 in terms of 𝚯-notation (theta of n notation) * n^3 / 1000n^2 - 100n + 3 * n^3 - n^2 - n ; drop lower order terms = 𝚯(n^3). 2.2-2 > Consider sorting `n` numbers stored in array `A` by first finding the smallest > element of `A` and exchanging it with the element in `A[1]`. Then find the > second smallest element of `A`, and exchange it with `A[2]`. Continue in this > manner for the first `n - 1` elements of `A`. Write pseudocode for *selection sort*. n = A.length for i = 1 to n - 1 { min = i for j = i + 1 to n { if A[j] < A[min] min = j A[i], A[min] = A[min], A[i] What loop invariant does this algorithm maintain? * intialization: inner loop initializes to the right index of the outer loop * maintenance: with the inner right array of the outer array. * termination: when end of loop is reached Why does it need to run for only the first n-1 elements, rather than for all `n` elements? * The last element of the array should has nothing to be compared against. Give the best-case and worst-case running times of selection sort in 𝚯-notation. = 𝚯(n^2). two loops, one nested within the other. 2.2-3: > Consider linear search again (see Exercise 2.1-3). How many elements of the > input sequence need to be checked on the average, assuming that the element > being searched for is equally likely to be any element in the array? How about > in the worst case? What are the average-case and worst-case running times of > linear search in 𝚯-notation? Justify your answers. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? Since there are `n` elements the average would be in the middle (.i.e. n/2). When we drop the lower order terms this becomes `𝚯(n)`. How about in the worst case? = 𝚯(n). In the worst case you need to search check every element in the input. What are the average-case and worst-case running times of linear search in 𝚯-notation? They are both 𝚯(n). 2.2-4: How can we modify almost any algorithm to have a good best-case running time? Reduce the input size by rejecting elements or hard code an early return if some condition is satisfied. Check for some particular input and if it receives that then returns some answer. i.e. cheating. Slow algorithm that works fast on some input. [Watch](http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1) * Performance * User friendliness Algorithms give you a language to talk about language behaviour. # 2.3 - Designing algorithms algorithm design techniques: * incremental approach (insertion sort) * divide and conquer 2.3.1 - The divide-and-conquer approach they break the problem down into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to creat a solution the original problem. Involves three steps at each level of the recursion: 1. Divide: the problem into a number of subproblems that are all smaller instances of the same problem. 1. Conquer: the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner. 1. Combine: the solutions to the subproblems into the solution for the original problem. The `merge sort` algorithm closely follows the divide-and-conquer paradigm. * Divide: dive the `n`-element sequence to be sorted into two subsequences of `n/2` elements each. * Conquer: Sort the two subsequences to produce the sorted answer. * Combine: Merge the two sorted subsequences to produce the sorted answer. The recursion "bottoms out" when the sequence to be sorted has length 1. Every sequence with length 1 is already sorted. The key operation of merge sort is mergin two sorted sequences in the "combine" step. `MERGE(A, p, q, r)` where `A` is an array and `p`, `q`, and `r` are indices into the array such that `p <= q < r`. Merging takes `𝚯(n)` time. ```plaintext MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+j] L[n1+1] = ∞ R[n2+1] = ∞ i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 ``` ```plaintext A: [2, 4, 5, 7, 1, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 4, 5, 7, 1, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 5, 7, 1, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 7, 1, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 3, 1, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 3, 4, 2, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 3, 4, 5, 3, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 3, 4, 5, 6, 6] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j A: [1, 2, 2, 3, 4, 5, 6, 7] k L: [2, 4, 5, 7, ∞] i R: [1, 2, 3, 6, ∞] j ``` We must show that this loop invariant holds prior to the first iteration of the `for` loop of lines 12-17, that each iteration of the loop maintains the invariant, and the invariant provides a useful property to show correctness when the loop terminates. Initialization: Prior to the first iteration we have `k = p`, so that the subarray `A[p..k-1]` is empty. ```plaintext for k = p to r ``` Maintenance: To see that each iteration maintains the loop invariant, we loop until we have reached the end of both `L` and `R`. ```plaintext for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 ``` Termination: When we reach the sentinal value for both L and R we stop. ``` MERGE-SORT(A,p,r) if p < r q = [(p+r)/2] MERGE-SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r) ``` Analyzing divide-and-conquer algorithms When an algorithm contains a recursive call to itself, we can often describe its running time by a `recurrence equation` or `recurrence`, which describes the overall running time on a problem of size `n` in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recurrence and provide bounds on the performance of the algorithm. ```plaintext Recursion Tree ----------------- |1|2|2|3|4|5|6|7| ----------------- / \ --------- --------- |2|4|5|7| |1|2|3|6| --------- --------- / \ / \ ----- ----- ----- ----- |2|5| |4|7| |1|3| |2|6| ----- ----- ----- ----- / \ / \ / | / \ - - - - - - - - |5| |2| |4| |7| |1| |3| |2| |6| - - - - - - - - ``` Running time: `T(n)` Analysis of merge sort 2.3-1: Using Figure 2.4 as a model, illustrate the operation of merge sort on the array `A = [3,41,52,26,38,57,9,49]`. ```plaintext ----------------------- |3|9|26|38|41|49|52|57| ----------------------- / \ ------------ ------------ |3|41|52|26| |38|57|9|49| ------------ ------------ / \ / \ ------ ------- ------- ------ |3|41| |52|26| |38|57| |9|49| ------ ------- ------- ------ / \ / \ / \ / \ - -- -- -- -- -- - -- |3| |41| |52| |26| |38| |57| |9| |49| - -- -- -- -- -- - -- ``` 2.3-2: Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array `L` or `R` has had all its elements copied back to `A` and then copying the remainder of the other array back into `A`. ```plaintext MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q for i = 1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+j] i = 1 j = 1 k = p while i < q and j < r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 k = k + 1 for k = k to r if j >= r A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 ``` 2.3-3: Use mathematical induction to show that when `n` is an exact power of 2, the solution of the recurrence ... is `T(n) = nlg(n)` ```plaintext 2 if n = 2 T(n) = { 2T(n/2) + n if n = 2**k, for k > 1 ``` ??? 2.3-4: We can express insertion sort as a recursive procedure as follows In order to sort `A[i..n]`, we recursively sort `A[i..n-1]` and then insert `A[n]` into the sorted array `A[1..n-1]`. Write a recurrence for the worst-case running time of this recursive version of insertion sort. 2.3-5: Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst case running time of binary search is O(lg(n)). `BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find. ```plaintext BINARY-SEARCH(A, t, s, e) length = e - s if length == 1 item = A[s] else mid = (length / 2) + s item = A[mid] if item == t return mid if item < t return BINARY-SEARCH(A, t, s, mid-1) else return BINARY-SEARCH(A, t, mid+1, e) ``` # Growth of Functions When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the _asymptotic_ efficiency of algorithms. ## Asymptotic Notation Natural numbers. `N = {0,1,2,...}`. This notation is useful for describing the worst case running time of function `T(n)`. ### 𝚯-notation (theta) The worst case running time of insertion sort is `T(n) = 𝚯(n^2)`. `f(n) = O(g(n))` means that there are some suitable constants `c > 0` and `n0 >0` such that f is bounded by c of g of n for all of n. Ex. `2*n^2 = O(n^3)` big o is like less than or equal to. set definitiion `2n^2` is in the set of `O(n^3)` Macro Convention: A set in a formula represents an anonymous function in that set. Ex. `f(n) = n^3 + O(n^2)`. This means that there is a function h(n) that is in big o of n squared such that `f(n) = n^3 th(n)`. WHAT... THE WHAT? Ex. `n^2 + O(n) = O(n^2)`. equals means `is`. is means everything over here means something over here. Everything on the left exists on the right side, but the right is not the same as the left side. Big omega notation. _()_ _()_(g(n)) = {f(n) there exists consts c > 0 * running time: `𝚯(n)`. Theta of n. * When we say that a particular running time is theta of n, we're saying that once `n` gets large enough, the running time is at least `k1*n` and at most `k2*n` for some constants `k1` and `k2`. * we don't have to worry about which time units we're using. * when we use big-𝚯 notation, we're saying that we have an *asymptotically tight bound* on the running time. * `𝚯(1)`: Constant time. * `𝚯(log n)`: * `𝚯(n)`: * `𝚯(nlog n)`: * `𝚯(n^2)`: * `𝚯(n^2 * log n)`: * `𝚯(n^3)`: * `𝚯(2^n)`: * `𝚯(n!)`: * rate of growth Abdul Bari https://www.youtube.com/watch?v=A03oI0znAoc Asymptotic Notations Big Oh - Omega - Theta Representing a simple form of a function We need a simple method for representing time complexity. | symbol | english | use | | -------- | --- | --- | | O | big-oh | upper bound of a function | | 𝚯 | theta notation | average bound of a function | | _()_ | big-omega | lower bound of a function | Theta is useful. class of functions | name | symbol | speed | | ------------- | --------- | ----- | | constant | 𝚯(1) | fast | | logarithmic | 𝚯(log n) | | | | | 𝚯(sqrt n) | | | | linear | 𝚯(n) | | | | | 𝚯(n logn) | | | | polynomial | 𝚯(n^2) | | | | | 𝚯(n^3) | | | | exponential | 𝚯(2^n) | | | | | 𝚯(3^n) | | | | factorial | 𝚯(n!) | V | | | 𝚯(n^n) | slow | 1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n Big-oh ------ The function `f(n) = O(g(n))` if there exists positive constants `c` and `n0` such that `0 <= f(n) <= c*g(n)` for all `n >= n0`. Example: ``` f(n) = 2n+3 2n+3 <= __ 10n __ n>=1 f(n) c*g(n) f(n) = O(n) 2n+3 <= 2n+3n will always work. ``` instead of guessing the value you can make it as 2n+3 Little-oh --------- The function `f(n) = o(g(n))` for any positive constant `c > 0`, if there exists a constant `n0 > 0` such that `0 < f(n) < c * g(n)` for all `n >= n0`. Omega ---- The function `f(n) = omega(g(n))` if there exists positive contstants c and n0 such that `0 <= c * g(n) <= f(n)` for all `n >= n0`. e.g. ``` f(n) = 2n+3 f(n) c * g(n) 2n+3 >= log n V n>=1 f(n) c * g(n) true f(n) = omega(n) (most useful answer) true f(n) = omega(logn) ``` little-omega w-notation ---------- Denotes a lower bound that is not asymptotically tight. The function `f(n) = w(g(n))` for any positive constant `c > 0`, if there exists a constant `n0 > 0` such that `0 <= c * g(n) < f(n)` for all `n >= n0` the relation `f(n) = w(g(n))` implies that: ```plaintext lim f(n) ---- = infinity n->infinity g(n) ``` if the limit exists. That is `f(n)` becomes arbitrarily large relative to `g(n)` as `n` approaches infinity. Theta ----- The function `f(n)=theta(g(n))` if there exists positive constants c1, c2, and n0 such that `0 <= c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`. (n0 is pronounced enn-not) f(n) = theta(g(n)) ``` eg. f(n) = 2n + 3 1*n <= 2n + 3 <= 5xn c*g(n) f(n) ``` omega <= theta <= big-oh | omega | theta | big-oh | | ----- | ----- | ------ | | omega(1) | | O(n^n) | | omega(1) | theta(log n!) | O(nlog n) | 1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n constant (1) ======== ```bash モ ruby -e '1.upto(100) { |n| puts 10 }' | asciigraph -h 32 -w 72 10.00 ┼─────────────────────────────────────────────────────────────────────── ``` logarithmic (logn) =========== ```bash モ ruby -e '1.upto(100) { |n| puts Math.log2(n) }' | asciigraph -h 32 -w 72 6.64 ┼ ╭──── 6.44 ┤ ╭────────╯ 6.23 ┤ ╭───────╯ 6.02 ┤ ╭──────╯ 5.81 ┤ ╭─────╯ 5.61 ┤ ╭────╯ 5.40 ┤ ╭───╯ 5.19 ┤ ╭───╯ 4.98 ┤ ╭──╯ 4.78 ┤ ╭──╯ 4.57 ┤ ╭─╯ 4.36 ┤ ╭──╯ 4.15 ┤ ╭╯ 3.94 ┤ ╭─╯ 3.74 ┤ ╭╯ 3.53 ┤ ╭─╯ 3.32 ┤ ╭╯ 3.11 ┤ │ 2.91 ┤ ╭╯ 2.70 ┤ ╭╯ 2.49 ┤ │ 2.28 ┤ ╭╯ 2.08 ┤ │ 1.87 ┤ ╭╯ 1.66 ┤ │ 1.45 ┤ │ 1.25 ┤╭╯ 1.04 ┤│ 0.83 ┤│ 0.62 ┤│ 0.42 ┤│ 0.21 ┤│ 0.00 ┼╯ ``` square root (n) =============== ```bash モ ruby -e '1.upto(100) { |n| puts Math.sqrt(n) }' | asciigraph -h 32 -w 72 10.00 ┤ ╭ 9.72 ┤ ╭───╯ 9.44 ┤ ╭───╯ 9.16 ┤ ╭──╯ 8.88 ┤ ╭───╯ 8.59 ┤ ╭──╯ 8.31 ┤ ╭───╯ 8.03 ┤ ╭──╯ 7.75 ┤ ╭──╯ 7.47 ┤ ╭──╯ 7.19 ┤ ╭──╯ 6.91 ┤ ╭──╯ 6.62 ┤ ╭──╯ 6.34 ┤ ╭─╯ 6.06 ┤ ╭──╯ 5.78 ┤ ╭─╯ 5.50 ┤ ╭──╯ 5.22 ┤ ╭─╯ 4.94 ┤ ╭─╯ 4.66 ┤ ╭─╯ 4.38 ┤ ╭─╯ 4.09 ┤ ╭╯ 3.81 ┤ ╭─╯ 3.53 ┤ ╭╯ 3.25 ┤ ╭─╯ 2.97 ┤ ╭╯ 2.69 ┤ ╭╯ 2.41 ┤ ╭╯ 2.12 ┤ ╭╯ 1.84 ┤ ╭╯ 1.56 ┤ │ 1.28 ┤╭╯ 1.00 ┼╯ ``` Linear (n) ========= ```bash 100.00 ┼ ╭─ 96.91 ┤ ╭──╯ 93.81 ┤ ╭─╯ 90.72 ┤ ╭─╯ 87.62 ┤ ╭─╯ 84.53 ┤ ╭─╯ 81.44 ┤ ╭──╯ 78.34 ┤ ╭─╯ 75.25 ┤ ╭─╯ 72.16 ┤ ╭─╯ 69.06 ┤ ╭──╯ 65.97 ┤ ╭─╯ 62.88 ┤ ╭─╯ 59.78 ┤ ╭─╯ 56.69 ┤ ╭─╯ 53.59 ┤ ╭──╯ 50.50 ┤ ╭─╯ 47.41 ┤ ╭─╯ 44.31 ┤ ╭─╯ 41.22 ┤ ╭─╯ 38.12 ┤ ╭──╯ 35.03 ┤ ╭─╯ 31.94 ┤ ╭─╯ 28.84 ┤ ╭─╯ 25.75 ┤ ╭──╯ 22.66 ┤ ╭─╯ 19.56 ┤ ╭─╯ 16.47 ┤ ╭─╯ 13.38 ┤ ╭─╯ 10.28 ┤ ╭──╯ 7.19 ┤ ╭─╯ 4.09 ┤╭─╯ 1.00 ┼╯ ``` n log(n) ======== ```bash モ ruby -e '1.upto(100) { |n| puts n * Math.log2(n) }' | asciigraph -h 32 -w 72 664 ┼ ╭ 644 ┤ ╭─╯ 623 ┤ ╭─╯ 602 ┤ ╭─╯ 581 ┤ ╭─╯ 561 ┤ ╭─╯ 540 ┤ ╭─╯ 519 ┤ ╭─╯ 498 ┤ ╭╯ 478 ┤ ╭─╯ 457 ┤ ╭─╯ 436 ┤ ╭─╯ 415 ┤ ╭─╯ 394 ┤ ╭─╯ 374 ┤ ╭─╯ 353 ┤ ╭─╯ 332 ┤ ╭─╯ 311 ┤ ╭─╯ 291 ┤ ╭──╯ 270 ┤ ╭─╯ 249 ┤ ╭─╯ 228 ┤ ╭─╯ 208 ┤ ╭─╯ 187 ┤ ╭─╯ 166 ┤ ╭──╯ 145 ┤ ╭─╯ 125 ┤ ╭──╯ 104 ┤ ╭─╯ 83 ┤ ╭──╯ 62 ┤ ╭─╯ 42 ┤ ╭──╯ 21 ┤ ╭───╯ 0 ┼──╯ ``` n^2 === ```bash 10000 ┼ ╭ 9688 ┤ ╭╯ 9375 ┤ ╭╯ 9063 ┤ ╭─╯ 8750 ┤ ╭╯ 8438 ┤ ╭╯ 8125 ┤ ╭╯ 7813 ┤ ╭╯ 7500 ┤ ╭─╯ 7188 ┤ ╭╯ 6875 ┤ ╭╯ 6563 ┤ ╭─╯ 6250 ┤ ╭╯ 5938 ┤ ╭─╯ 5625 ┤ ╭╯ 5313 ┤ ╭─╯ 5000 ┤ ╭╯ 4688 ┤ ╭─╯ 4376 ┤ ╭─╯ 4063 ┤ ╭╯ 3751 ┤ ╭─╯ 3438 ┤ ╭─╯ 3126 ┤ ╭─╯ 2813 ┤ ╭─╯ 2501 ┤ ╭──╯ 2188 ┤ ╭─╯ 1876 ┤ ╭─╯ 1563 ┤ ╭──╯ 1251 ┤ ╭───╯ 938 ┤ ╭──╯ 626 ┤ ╭────╯ 313 ┤ ╭─────╯ 1 ┼────────╯ ``` n^3 === ```bash モ ruby -e '1.upto(100) { |n| puts n ** 3 }' | asciigraph -h 32 -w 72 1000000 ┼ ╭ 968750 ┤ ╭╯ 937500 ┤ │ 906250 ┤ ╭╯ 875000 ┤ ╭╯ 843750 ┤ ╭╯ 812500 ┤ ╭╯ 781250 ┤ ╭╯ 750000 ┤ ╭╯ 718750 ┤ │ 687500 ┤ ╭╯ 656250 ┤ ╭╯ 625000 ┤ ╭╯ 593750 ┤ ╭╯ 562500 ┤ ╭─╯ 531250 ┤ ╭╯ 500000 ┤ ╭╯ 468751 ┤ ╭╯ 437501 ┤ ╭╯ 406251 ┤ ╭─╯ 375001 ┤ ╭╯ 343751 ┤ ╭─╯ 312501 ┤ ╭╯ 281251 ┤ ╭─╯ 250001 ┤ ╭─╯ 218751 ┤ ╭─╯ 187501 ┤ ╭─╯ 156251 ┤ ╭──╯ 125001 ┤ ╭──╯ 93751 ┤ ╭───╯ 62501 ┤ ╭───╯ 31251 ┤ ╭───────╯ 1 ┼─────────────────╯ ``` 2^n === ```bash モ ruby -e '1.upto(100) { |n| puts 2 ** n }' | asciigraph -h 32 -w 72 1267650600228229401496703205376 ┼ ╭ 1228036518971097232699931230208 ┤ │ 1188422437713965063903159255040 ┤ │ 1148808356456832895106387279872 ┤ │ 1109194275199700726309615304704 ┤ │ 1069580193942568557512843329536 ┤ │ 1029966112685436388716071354368 ┤ │ 990352031428304219919299379200 ┤ │ 950737950171172051122527404032 ┤ │ 911123868914039882325755428864 ┤ │ 871509787656907713528983453696 ┤ │ 831895706399775544732211478528 ┤ │ 792281625142643375935439503360 ┤ │ 752667543885511207138667528192 ┤ │ 713053462628379038341895553024 ┤ │ 673439381371246869545123577856 ┤ │ 633825300114114700748351602688 ┤ │ 594211218856982531951579627520 ┤ │ 554597137599850363154807652352 ┤ │ 514983056342718194358035677184 ┤ ╭╯ 475368975085586025561263702016 ┤ │ 435754893828453856764491726848 ┤ │ 396140812571321687967719751680 ┤ │ 356526731314189519170947776512 ┤ │ 316912650057057350374175801344 ┤ │ 277298568799925181577403826176 ┤ │ 237684487542793012780631851008 ┤ │ 198070406285660843983859875840 ┤ ╭╯ 158456325028528675187087900672 ┤ │ 118842243771396506390315925504 ┤ │ 79228162514264337593543950336 ┤ ╭╯ 39614081257132168796771975168 ┤ ╭╯ 0 ┼──────────────────────────────────────────────────────────────────╯ ``` 3^n === ```bash モ ruby -e '1.upto(100) { |n| puts 3 ** n }' | asciigraph -h 32 -w 72 515377520732011324194596268868618440852459487232 ┼ ╭ 499271973209135955101707932727721296615381663744 ┤ │ 483166425686260586008819596586824152378303840256 ┤ │ 467060878163385298045569675052608703930231160832 ┤ │ 450955330640509928952681338911711559693153337344 ┤ │ 434849783117634559859793002770814415456075513856 ┤ │ 418744235594759190766904666629917271218997690368 ┤ │ 402638688071883821674016330489020126981919866880 ┤ │ 386533140549008533710766408954804678533847187456 ┤ │ 370427593026133164617878072813907534296769363968 ┤ │ 354322045503257795524989736673010390059691540480 ┤ │ 338216497980382426432101400532113245822613716992 ┤ │ 322110950457507057339213064391216101585535893504 ┤ │ 306005402934631728811143935553659805242960642048 ┤ │ 289899855411756359718255599412762661005882818560 ┤ │ 273794307888881031190186470575206364663307567104 ┤ │ 257688760366005662097298134434309220426229743616 ┤ │ 241583212843130293004409798293412076189151920128 ┤ │ 225477665320254964476340669455855779846576668672 ┤ │ 209372117797379595383452333314958635609498845184 ┤ │ 193266570274504266855383204477402339266923593728 ┤ │ 177161022751628897762494868336505195029845770240 ┤ │ 161055475228753528669606532195608050792767946752 ┤ │ 144949927705878159576718196054710906555690123264 ┤ │ 128844380183002790483829859913813762318612299776 ┤ ╭╯ 112738832660127502520579938379598313870539620352 ┤ │ 96633285137252133427691602238701169633461796864 ┤ │ 80527737614376764334803266097804025396383973376 ┤ │ 64422190091501395241914929956906881159306149888 ┤ │ 48316642568626026149026593816009736922228326400 ┤ │ 32211095045750738185776672281794288474155646976 ┤ ╭╯ 16105547522875369092888336140897144237077823488 ┤ │ 0 ┼────────────────────────────────────────────────────────────────────╯ ``` factorial ========= ```bash モ ruby -e '1.upto(100) { |n| puts (1..n).reduce(:*) || 1 }' | asciigraph -h 32 -w 72 93326215443944150965646704795953882578400970373184098831012889540582227238570431295066113089288327277825849664006524270554535976289719382852181865895959724032 ┼ ╭ 90409771211320894723678960937099742018530417689077610513736049894308587881917371125019252709659385351025577475535631344215463015406338066470094307934227922944 ┤ │ 87493326978697638481711217078245601458659865004971122196459210248034948525264310954972392330030443424225305287064738417876390054522956750088006749972496121856 ┤ │ 84576882746074382239743473219391460898789312320864633879182370601761309168611250784925531950401501497425033098593845491537317093639575433705919192010764320768 ┤ │ 81660438513451125997775729360537320338918759636758145561905530955487669811958190614878671570772559570624760910122952565198244132756194117323831634049032519680 ┤ │ 78743994280827881950138260173527833613412385832207539075090186094257588498887003981440165955853071238770203813417571981933120864867433486285399073307165196288 ┤ │ 75827550048204625708170516314673693053541833148101050757813346447983949142233943811393305576224129311969931624946679055594047903984052169903311515345433395200 ┤ │ 72911105815581369466202772455819552493671280463994562440536506801710309785580883641346445196595187385169659436475786129254974943100670853521223957383701594112 ┤ │ 69994661582958113224235028596965411933800727779888074123259667155436670428927823471299584816966245458369387248004893202915901982217289537139136399421969793024 ┤ │ 67078217350334856982267284738111271373930175095781585805982827509163031072274763301252724437337303531569115059534000276576829021333908220757048841460237991936 ┤ │ 64161773117711600740299540879257130814059622411675097488705987862889391715621703131205864057708361604768842871063107350237756060450526904374961283498506190848 ┤ │ 61245328885088344498331797020402990254189069727568609171429148216615752358968642961159003678079419677968570682592214423898683099567145587992873725536774389760 ┤ │ 58328884652465100450694327833393503528682695923018002684613803355385671045897456327720498063159931346114013585886833840633559831678384956954441164794907066368 ┤ │ 55412440419841832014396309302694709134447964359355632536875468924068473645662522621065282918821535824368026305650428571220537177800382955228698609613310787584 ┤ │ 52495996187218587966758840115685222408941590554805026050060124062838392332591335987626777303902047492513469208945047987955413909911622324190266048871443464192 ┤ │ 49579551954595331724791096256831081849071037870698537732783284416564752975938275817579916924273105565713197020474155061616340949028241007808178490909711663104 ┤ │ 46663107721972075482823352397976941289200485186592049415506444770291113619285215647533056544644163638912924832003262135277267988144859691426090932947979862016 ┤ │ 43746663489348819240855608539122800729329932502485561098229605124017474262632155477486196165015221712112652643532369208938195027261478375044003374986248060928 ┤ │ 40830219256725562998887864680268660169459379818379072780952765477743834905979095307439335785386279785312380455061476282599122066378097058661915817024516259840 ┤ │ 37913775024102306756920120821414519609588827134272584463675925831470195549326035137392475405757337858512108266590583356260049105494715742279828259062784458752 ┤ │ 34997330791479050514952376962560379049718274450166096146399086185196556192672974967345615026128395931711836078119690429920976144611334425897740701101052657664 ┤ │ 32080886558855806467314907775550892324211900645615489659583741323966474879601788333907109411208907599857278981414309846655852876722573794859308140359185334272 ┤ │ 29164442326232550225347163916696751764341347961509001342306901677692835522948728163860249031579965673057006792943416920316779915839192478477220582397453533184 ┤ │ 26247998093609293983379420057842611204470795277402513025030062031419196166295667993813388651951023746256734604472523993977706954955811162095133024435721732096 ┤ │ 23331553860986037741411676198988470644600242593296024707753222385145556809642607823766528272322081819456462416001631067638633994072429845713045466473989931008 ┤ │ 20415109628362781499443932340134330084729689909189536390476382738871917452989547653719667892693139892656190227530738141299561033189048529330957908512258129920 ┤ │ 17498665395739525257476188481280189524859137225083048073199543092598278096336487483672807513064197965855918039059845214960488072305667212948870350550526328832 ┤ │ 14582221163116269015508444622426048964988584540976559755922703446324638739683427313625947133435256039055645850588952288621415111422285896566782792588794527744 ┤ │ 11665776930493024967870975435416562239482210736425953269107358585094557426612240680187441518515767707201088753883571705356291843533525265528350231846927204352 ┤ │ 8749332697869768725903231576562421679611658052319464951830518938820918069959180510140581138886825780400816565412678779017218882650143949146262673885195403264 ┤ │ 5832888465246512483935487717708281119741105368212976634553679292547278713306120340093720759257883853600544376941785852678145921766762632764175115923463602176 ┤ │ 2916444232623256241967743858854140559870552684106488317276839646273639356653060170046860379628941926800272188470892926339072960883381316382087557961731801088 ┤ │ 0 ┼──────────────────────────────────────────────────────────────────────╯ ``` n^n === ```bash モ ruby -e '1.upto(100) { |n| puts n ** n }' | asciigraph -h 32 -w 72 99999999999999996973312221251036165947450327545502362648241750950346848435554075534196338404706251868027512415973882408182135734368278484639385041047239877871023591066789981811181813306167128854888448 ┼ ╭ 96874999999999993881068257436338693624063265494893649837925489870956970225278181471331343664445725062176639061598984569590467075190263689914928232598270195230434231246428683216594756627990091887804416 ┤ │ 93749999999999990788824293621641221300676203444284937027609228791567092015002287408466348924185198256325765707224086730998798416012248895190471424149300512589844871426067384622007699949813054920720384 ┤ │ 90625000000000004692996099943490907044111751072672298764272734977198756186938815758515269731196439103674964840186330296865673316722266591556553420586962491053894832136501348230021310004219026968936448 ┤ │ 87500000000000001600752136128793434720724689022063585953956473897808877976662921695650274990935912297824091485811432458274004657544251796832096612137992808413305472316140049635434253326041990001852416 ┤ │ 84374999999999998508508172314095962397337626971454873143640212818418999766387027632785280250675385491973218131436534619682335998366237002107639803689023125772716112495778751040847196647864953034768384 ┤ │ 81249999999999995416264208499398490073950564920846160333323951739029121556111133569920285510414858686122344777061636781090667339188222207383182995240053443132126752675417452446260139969687916067684352 ┤ │ 78124999999999992324020244684701017750563502870237447523007690659639243345835239507055290770154331880271471422686738942498998680010207412658726186791083760491537392855056153851673083291510879100600320 ┤ │ 74999999999999997729984165938277124460587745659126771986181313212760136326665556650647253803529688901020634311980411806136601800776208863479538780785429908403267693300092486358386359979625346641166336 ┤ │ 71875000000000003135948087191853231170611988448016096449354935765881029307495873794239216836905045921769797201274084669774204921542210314300351374779776056314997993745128818865099636667739814181732352 ┤ │ 68750000000000000043704123377155758847224926397407383639038674686491151097219979731374222096644519115918923846899186831182536262364195519575894566330806373674408633924767520270512579989562777214648320 ┤ │ 65624999999999996951460159562458286523837864346798670828722413607101272886944085668509227356383992310068050492524288992590867603186180724851437757881836691033819274104406221675925523311385740247564288 ┤ │ 62499999999999993859216195747760814200450802296189958018406152527711394676668191605644232616123465504217177138149391153999198944008165930126980949432867008393229914284044923081338466633208703280480256 ┤ │ 59374999999999999265180117001336920910475045085079282481579775080832287657498508749236195649498822524966340027443064017636802064774167380947793543427213156304960214729081255588051743321323170821046272 ┤ │ 56249999999999996172936153186639448587087983034470569671263514001442409447222614686371200909238295719115466673068166179045133405596152586223336734978243473664370854908719956993464686643146133853962240 ┤ │ 53125000000000001578900074440215555297112225823359894134437136554563302428052931829963163942613652739864629562361839042682736526362154037044149328972589621576101155353756289500177963331260601394528256 ┤ │ 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 ┤ │ 46874999999999995394412146810820610650338101722142468513804614395783546007501143704233174462092599128162882853612043365499399208006124447595235712074650256294922435713033692311003849974906527460360192 ┤ │ 43750000000000000800376068064396717360362344511031792976978236948904438988331460847825137495467956148912045742905716229137002328772125898416048306068996404206652736158070024817717126663020995000926208 ┤ │ 40624999999999997708132104249699245036975282460423080166661975869514560778055566784960142755207429343061172388530818390545333669594111103691591497620026721566063376337708726223130069984843958033842176 ┤ │ 37500000000000003114096025503275351746999525249312404629835598422635453758885883928552105788582786363810335277824491254182936790360112554512404091614372869477793676782745058729843346672958425574408192 ┤ │ 34375000000000000021852061688577879423612463198703691819519337343245575548609989865687111048322259557959461923449593415591268131182097759787947283165403186837204316962383760135256289994781388607324160 ┤ │ 31249999999999996929608097873880407100225401148094979009203076263855697338334095802822116308061732752108588569074695576999599472004082965063490474716433504196614957142022461540669233316604351640240128 ┤ │ 28125000000000002335572019127456513810249643936984303472376698816976590319164412946414079341437089772857751458368368440637202592770084415884303068710779652108345257587058794047382510004718819180806144 ┤ │ 24999999999999999243328055312759041486862581886375590662060437737586712108888518883549084601176562967006878103993470602045533933592069621159846260261809969467755897766697495452795453326541782213722112 ┤ │ 21875000000000004649291976566335148196886824675264915125234060290707605089718836027141047634551919987756040993287143465683137054358071071980658854256156117379486198211733827959508730014656249754288128 ┤ │ 18750000000000001557048012751637675873499762624656202314917799211317726879442941964276052894291393181905167638912245627091468395180056277256202045807186434738896838391372529364921673336479212787204096 ┤ │ 15624999999999998464804048936940203550112700574047489504601538131927848669167047901411058154030866376054294284537347788499799736002041482531745237358216752098307478571011230770334616658302175820120064 ┤ │ 12499999999999995372560085122242731226725638523438776694285277052537970458891153838546063413770339570203420930162449949908131076824026687807288428909247069457718118750649932175747559980125138853036032 ┤ │ 9374999999999992280316121307545258903338576472830063883969015973148092248615259775681068673509812764352547575787552111316462417646011893082831620460277386817128758930288633581160503301948101885952000 ┤ │ 6250000000000006184487927629394944646774124101217425620632522158779756420551788125729989480521053611701746708749795677183337318356029589448913616897939365281178719640722597189174113356354073934168064 ┤ │ 3125000000000003092243963814697472323387062050608712810316261079389878210275894062864994740260526805850873354374897838591668659178014794724456808448969682640589359820361298594587056678177036967084032 ┤ │ 0 ┼──────────────────────────────────────────────────────────────────────╯ ``` https://www.udemy.com/course/datastructurescncpp/learn/lecture/13319452#overview Asymptotic Notation Video | 1 < lg n < n < n lg n < n^2 < n^3 < .... < 2^n < 3^n ... < n^n | | polynomial | | exponential | 1 : push into stack lg n : AVL tree n : max item in array n log n : quick sort n^2 : matrix, graph 2^n : exponential time complexities Don't start n from n = 0 or n = 1. Starting value of n can be any starting value n 0 --|---- infinity |------------ | n^3 | 2^n | | --- | ---- | | 2^3=8 | 2^2=4 | | 10^3=1000 | 2^10=1024 | | 11^3=1221 | 2^11=2048 | f(n) = n ---> O(n) f(n) = n^2 ---> O(n^2) f(n) = n sigma i ----- 1 + 2 + 3 + .... + n = ((n(n+1))/2) = O(n^2) i=1 | lower bound | omega | | upper bound | big-oh | | tight bound | theta | Useful when you cannot get the exact polynomial for a function. ## Dynamic Programming Dynamic Programming means tabular programming or Dynamic Planning. This term was created before coding style programming was a thing. This is a design technique used to solve a class of problems. Example: Longest Common Subsequence (LCS) Important in computation biology like finding commonalities in two DNA strings. Given two sequences `x[1...m]` and `y[1..n]`, find *a* longest sequence common to both. "a", not "the" LCS. ```plaintext x: A B C B D A B | BDB y: B D C A B A | BAB | BDAB | BCAB | BCBA = LCS(x, y) * functional notation but not a function it's a relation. * classic misuse of notation ``` Brute force algorithm for solving this algorithm. * check every subsequence of x from 1..m (`x[1..m]`) to see if it's also a subsequence of `y[i..n]` * analysis check: * Q: How long does it take me to see if it's a subsequence of y? * A: The length of y which is `O(n)`. * Check = `O(n)` * Q: How many subsequences of `x` are there? * A: 2^m subsequences of `x` * running time: `O(n*2^m)` (exponential time = slow!) Simplification: 1. Look at length of `LCS(y, y)`. 2. Extend the algorithm to find LCS itself. Notation: `|s|` denotes length of seq s. 15.1 Dynamic Programming Dynamic Programming, like the divide and conquer method, solves problems by combining solutions to subproblems. Divide and conquer algorithms partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. Is like recursivion but also when the subproblems overlap so we don't have to recompute the same answer over and over. We save answers to a table to avoid recompute. It applies to optimization problems. * it can have many solutions * wish to find optimal solution * "an" optimal solution not "the" solution. Steps: 1. characterize the structure of an optimal solution 1. recursively define the value of an optimal solution 1. compute the value of "an" optimal solution. (bottom-up) 1. construct optimal solution from computed information. 15.1 Rod-cutting Problem Where to cut steel rods to make the most revenue? * cuts are free * i = 1,2,... to price pi in $ for length i given a rod of length n inches and a table of prices pi for i = 1,2...n determine the max revenue rn obtainable by cutting up the rods and selling pieces if pn for a rod is length n is large enough, no cutting might be necessary. Recursive top down approach: exponential time 2^n ```plaintext CUT-ROD(p, n) if n == 0 return 0 q = -1 for i = 1 to n q = max(q, p[i] + CUT-ROD(p, n-i)) return q ``` DP - time-memory trade-off. * exponential solution might be turned into polynomial solution. TOP down solution: ```plaintext MEMOIZED-CUT-ROD(p, n) let r[0..n] be a new array for i = 0 to n r[i] = -1 return MEMOIZED-CUT-ROD-AUX(p, n, r) MEMOIZED-CUT-ROD-AUX(p, n, r) return r[n] if r[n] >= 0 return 0 if n == 0 q = -1 for i = 1 to n q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r) r[n] = q return q ``` BOTTOM up solution: ```plaintext BOTTOM-UP-CUT-ROD(p, n) let r[0..n] be a new array r[0] = 0 for j = 1 to n q = -1 for i = 1 to j q = max(q, p[i] + r[j - i]) r[j] = q return r[n] ``` Extended solution that prints max revenue and the # of cuts needed for each length to produce that revenue. ```plaintext EXTENDED-BOTTOM-UP-CUT-ROD(p, n) let r = [0..n] let s = [1..n] r[0] = 0 for j = 1 to n q = -1 for i = 1 to j if q < p[i] + r[j-1] q = p[i] + r[j-1] s[j] = i r[j] = q return r, s PRINT-CUT-ROD-SOLUTION(p,n) (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n) while n > 0 print s[n] n = n - s[n] ```