1. Complexity Analysis (link to the post on comments) >> Why do complexity analysis? - Complexity is one of the metric performance that is easily measurable by just looking at our program. - It tells us how well our program will scale when the size of input increases. >> What are included in complexity analysis? - Time complexity Estimates how much time our program takes to process all inputs. - Space complexity Estimates how much space our program takes to process all inputs. >> How do we represent the complexity of a program? - Big O Also called upper bound, worst case complexity, denoted by O(...). - Omega Also called lower bound, best case complexity, denoted by Ω(...). - Theta Also called tight bound where upper bound and lower bound are equal, denoted by Θ(...) (not sure what this is used for outside academia purposes) These notations are usually followed by function of ‘N’, e.g. O(N), O(N²) where N denotes size of our input. We will only discuss about big O complexity here. >> Why? Consider bubble sort on input [1, 2, 3, 4, 5, 6, 7, 8, 9] We don’t have to sort anything, because the input is already sorted. This is called the best case complexity. This is not a useful concept because we can just pick any special input for the program and get O(1) as best case. What if we are unlucky that we get [9, 8, 7, 6, 5, 4, 3, 2, 1] as our input? Then we will have to swap every element: 9 with 8, 9 with 7, 9 with 6, ... 9 with 1. 8 with 7, 8 with 6, 8 with 5, ... 8 with 1. 7 with 6, 7 with 5, 7 with 4, ... 7 with 1. ... 2 with 1. So, the total operation takes N + (N-1) + (N-2) + .... + 1 = N² + N operation. This is what we care about, because it demonstrates the upper bound complexity of our program. (It can’t get any slower than that.) >> How do we measure space complexity? A program that requires no additional space is said to take O(1) space. If we need to create an additional array of size (N), our space complexity becomes O(N). If we need to create an additional 2D array of size (M x N), our space complexity becomes O(MN). >> How do we measure time complexity? A single instruction takes constant time O(1). If there are fixed number of instructions, then the collective instructions still count as O(1). The following code runs in O(1): a = b + 1 c = 2 * a If there is just 1 loop, the total time complexity can be obtained by multiplying the time complexity of the instructions inside the loop by the number of loop. The following code runs in O(N), because each instruction takes O(1) and they are executed N times: for (int i = 0; i < N; i++) { a = b + 1; c = 2 * a; } This runtime is also called linear time, because roughly, for (N) inputs, your program will also take (N) time (multiplied by some constants). If there are nested loops, the total complexity can be obtained by multiplying the number of outer loop by the number of inner loop. The following code runs in O(MN): for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // O(1) instructions here } } If we have time complexity of O(½N), or O(5N), or O(N + 6) times, the time complexity will still be counted as O(N). Remember, time complexity only measures how our program scales with input size (N). Similarly, if we have time complexity of O(N² + N), then we just take the bottleneck which is O(N²), so the time complexity becomes O(N²). The time complexity of a recursive function is determined by how many functions are called in each call, and the time complexity of instructions in each call. For example: void print(int n) { if (n == 0) return; cout << n; print(n - 1); } One call of print(n) will call the function (n) times, and the time complexity of each call is O(1). So, the time complexity will be O(n). Another example: void print(int n) { if (n == 0) return; cout << n; print(n - 1); print(n - 1); } There are 2 calls on print(n), then 4 calls on print(n - 1), then 8 calls on print(n - 2), and so on until (n) reaches 0. So, the total time complexity would be: 1 + 2 + 4 + 8 + ... + 2ⁿ⁻︎¹ = 2ⁿ - 1 = O(2ⁿ) >> What are the common time complexities? From the fastest to slowest: - Constant: O(1) - Logarithmic: O(log(N)) In computer science, logarithmic time is often referred as ²log(N). The code that runs in this complexity usually halves the input at each iteration. So, if we have an array of 1000 numbers in the beginning, next iteration we will only need to process 500 numbers, then 250 numbers, and so on. - Square root: O(sqrt(N)) Slower than logarithmic time, but faster than linear time. - Linear time: O(N) If we need to access each element in the array at least once, this is often the best possible time complexity. - O(N log(N)) This time complexity usually implies that the algorithm needs to sort the container. Merge sort has O(N log(N)) time complexity, which is the upper bound for comparison-based sorting. - Quadratic time: O(N²) This time complexity often indicates that we have a nested loop, e.g. when we need to go through each pair in the array. - O(2ⁿ) This time complexity tells us that the algorithm runs recursively. Other possibility might be that it goes through each subset of input elements. For example: [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]. - O(n!) This is most likely an algorithm that involves going through each permutation of all elements. For example: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] >> How do we estimate the appropriate time complexity if we know the size of input? Assuming that modern cpu takes few seconds to execute 10⁸︎ operations, then these are the allowed (worst) time complexity for various inputs. These numbers are based on online judges. - N <= 10: O(N!) - N <= 20: O(2ⁿ) - N <= 200: O(N³) - N <= 2000: O(N²) - N <= 10⁶︎: O(N log(N)) or O(N) - N > 10⁶︎: O(log(N)) or O(1) Final note: When comparing 2 programs with the same time complexity, one can be faster than the other, depending on hidden constant factors. For example, consider sorting a vector and using priority queue (binary heap) to sort elements. They both have the same time complexity, but the first is faster. Only use time complexity to estimate the appropriate runtime for your program, given the size of inputs. Exercise: Estimate the time complexity of these tasks. Assume we are doing these tasks naively, without advanced algorithms. - Finding the largest element in an array of size (N) - Finding the 10 largest element in an array of size (N) - Finding out whether a string of size (M) is a substring of size (N) - Finding out all positions of a substring size (M) in a string of size (N) - Finding out all solutions of a³ + b³ = c³ + d³ for 0 <= a, b, c, d <= N - Finding out whether there is a 2D submatrix of size 2x2 that has mean 20 in a 2D matrix of size (M x N). - Finding out whether there is a 2D submatrix that has mean 20 in a 2D matrix of size (M x N).

[Tutorial] 1. Complexity Analysis