****************** Algorithm Analysis ****************** An algorithm is a clearly specified set of simple instructions to solve a problem. There are different ways to solve the same problem, so different algorithms. Consider that two students propose their own algorithm to find the optimal path in a maze. * How can we compare these algorithms? * Which one is better? * In terms of computation time? * In terms of memory consumption? * How does it scale? Mathematical Background ======================= To estimate the time or the memory consumption, we need some tools, mathematical tools. Given two functions, there are usually points where one function is smaller than the other. So it doesn't make sense to claim that :math:`f(x) < g(x)`. What we really want is to compare their relative **rates of growth**. Before continuing, we need to define some things first. **Definition 1** :math:`T(N) = O(f(N))` if there are positive *constant* :math:`c` and :math:`n_0` such that :math:`T(N)\leq cf(N)` when :math:`N \geq n_0`. This is what we call the **Big-Oh notation**. .. admonition:: Example :class: example * Consider an algorithm that needs :math:`T(N) = n^2 + 5n + 25` operations. * We want to show that the algorithm Is :math:`O(n^2)`. * So we want to show that: * there are constants :math:`n_0` and :math:`c` * such that for all :math:`n>n_0`, :math:`cn^2 > n^2 + 5n + 25`. One way we can do this is finding a point where: .. math:: cn^2 = n^2 + 5n + 25 Consider :math:`n_0 = n` then we calculate: .. math:: c = 1 + \frac{5}{n_0} + \frac{25}{n_0^2} We can easily evaluate it for :math:`n_0 = 5`, and it gives us :math:`c=3`. S0 :math:`3n^2 > n^2 + 5n + 25`, for :math:`n>5` Usually we do not apply this definition formally. When we say that :math:`T(N) = O(f(N))`, we are guaranteeing that the function :math:`T(N)` grows at a rate not faster than :math:`f(N)`. Meaning than :math:`f(N)` is an upper bound on :math:`T(N)`. .. admonition:: Example :class: example :math:`N^3` grows faster than :math:`N^2`, so we can say :math:`N^2 = O(N^3)`. To make it easier we have a set of rules. **Rule 1** If :math:`T_1(N)=O(f(N))` and :math:`T_2(N) = O(g(N))`, then a. :math:`T_1(N) + T_2(N) = O(f(N)+g(N))`, intuitively it is :math:`O(\max(f(N),g(N)))` b. :math:`T_1(N)\times T_2(N) = O(f(N)\times g(N))` **Rule 2** If :math:`T(N)` is a polynomial of degree :math:`k`, then :math:`T(N) = O(N^k)`. **Rule 3** :math:`log^k N = O(N)` for any constant :math:`k`. It tells us that logarithms grow very slowly. It is sufficient to arrange most of the common functions by the growth rate: +---------------+------------+ |Function | Name | +===============+============+ |c | Constant | +---------------+------------+ |:math:`log N` | Logarithmic| +---------------+------------+ |:math:`log^2 N`| Log-squared| +---------------+------------+ |:math:`N` | Linear | +---------------+------------+ |:math:`N^2` | Quadratic | +---------------+------------+ |:math:`N^3` | Cubic | +---------------+------------+ |:math:`2^N` | Exponential| +---------------+------------+ .. important:: As you can see what we want is to know is the growth rate is compared to the size of the input :math:`N`. If we were comparing algorithms to sort elements in a list. Depending of the time complexity and the number of elements, the running time to sort the list can be very different: .. figure:: ./FG_02_004-1.png :align: center | Or to give another idea: .. figure:: ./complexity.png :align: center | Running-Time Calculation ======================== There are several ways to estimate the running time of a program. The previous table was obtained empirically, meaning runs the algorithms and compare the results. To simplify the analysis we will always consider that there is no particular unit of time. We just want to calculate for an algorithm the Big-Oh running time. * We throw away the low-order terms. * We never underestimate the running time of the program. It should never finish after this upper bound. Simple Example -------------- Here is a simple program function to calculate :math:`\sum_{i=1}^N i^3`. .. code-block:: java :linenos: int sum(int n){ int partialSum; partialSum = 0; for (int i = 1; i <= n; i++){ partialSum += i*i*i; } return partialSum; } .. admonition:: Activity :class: activity * How many units of time does it cost to declare a variable? (line 2) * How many units of time for line 4 and 8? * How many units of time for line 6 when executed once? How many times is it executed? * How many for line 5? * The total? And the corresponding Big-Oh? General Rules ------------- We will four rules to estimate the running time of an algorithm. **Rule 1 -- For loops** The running time of a :code:`for` loop is at most of the running time of the statement inside the :code:`for` loop (including tests) times the number of iterations. **Rule 2 -- Nested loops** The total running time of the statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops. .. admonition:: Example :class: example The following code has a running time of :math:`O(n^2)`. .. code-block:: java k = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ k++; } } **Rule 3 -- Consecutive Statements** The running time of consecutive statements is just the sum of the running time of each statement. .. admonition:: Example :class: example The following code is :math:`O(n^2)`. .. code-block:: java for (int i = 0; i < n; i++){ a[i] = 0; } for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ a[i] += a[j] + i + j; } } It has a first :code:`for` loop that run in :math:`O(n)`. The second run in :math:`O(n^2)`. **Rule 4 -- If/Else** The if/else statement is not as simple as it seems. Usually these statements have the following structure: .. code-block:: java if ( condition ){ statement_1 } else{ statement_2 } The running time cannot be more than the running time of the statement plus the larger running time between :code:`statement_1` and :code:`statement_2`. .. important:: Calculating it this way can overestimate the running time, but not underestimate it. What happen if there is a recursion? It depends on the type of recursion. Some are just a :code:`for` loop, such as the following function: .. code-block:: java :linenos: long factorial(int n){ if(n <= 1){ return 1; } else{ return n * factorial(n-1); } } In this case, we can calculate the running time of the :code:`for` loop (In this case :math:`O(n)`). Other recursion cannot be transformed into a simple loop. .. code-block:: java :linenos: long fib(int n){ if (n <= 1){ return 1; } else{ return fib(n-1) + fib(n-2); } } The analysis is simple. * Let :math:`T(N)` be the running time for :code:`fib(n)`. * If :math:`N=0` or :math:`N=1` * Then the running time is some constant value * :math:`T(0) = T(1) = 1`. * For :math:`N > 2` * The time to execute the function is the constant work of line 2. * Plus the work on line 6. * It consists of the addition of two function calls. * :code:`fib(n-1)`, so :math:`T(N-1)` * :code:`fib(n-2)`, so :math:`T(N-2)` * it gives us a total running time of :math:`T(N) = T(N-1) + T(N-2) + 2` We can prove that for :math:`N > 4, fib(N) \geq \frac{3}{2}^N`. This recursion function is growing exponentially with the size of the input. .. admonition:: Activity :class: activity Discuss and gives some idea why this function is growing exponentially. Maximum Subsequence Sum Problem =============================== We will take a very practical problem. One that is very **very** common in technical interview. Maximum Subsequence Sum Problem Given an array of integers os size :math:`N`. Find the continuous subarray that maximize the value :math:`\sum_{k=i}^j A_k`. .. admonition:: Example :class: example For the array :code:`[-2, 11, -4, 13, -5, -2]`, the answer is 20 (from :code:`a[1]` to :code:`a[3]`). A first algorithm ----------------- It is very easy to come with a first algorithm: .. literalinclude:: ./AlgorithmAnalysis.java :language: java :linenos: :lines: 68-90 :caption: Algorithm 1 .. admonition:: Activity :class: activity 1. Convince yourself that this algorithm works. 2. Analyze the running time. 3. Can we do better? A second algorithm ------------------ It is possible to avoid the cubic running time by removing a :code:`for` loop. Of course most of the time it's not possible, but in this case there is an inefficiency. Notice that in the previous algorithm (line 13) is calculating :math:`\sum_{k=i}^j a_k`. Which is the equivalent of :math:`a_j + \sum_{k=i}^{j-1} a_k` making algorithm 1 inefficiency. We then can deduce a more efficient algorithm: .. literalinclude:: ./AlgorithmAnalysis.java :language: java :linenos: :lines: 92-113 :caption: Algorithm 2 .. admonition:: Activity :class: activity 1. Convince yourself that this algorithm works. 2. Analyze the running time. 3. Can we do better? Divide-and-Conquer ------------------ For this problem, we can use a **divide-and-conquer** strategy. The idea: * The divide part: * We split the problem on two suproblems. * We solve each subproblem recursively. * The conquer part: * Joining the two solutions. * Doing additional work. In this problem, the maximum subsequence sum can be in one of three places. * It occurs entirely in the left part. * It occurs entirely in the right part. * It occurs in both parts. Consider the example: +------------+------------+ | First half | Second half| +------------+------------+ |4 -3 5 -2 | -1 2 6 -2 | +------------+------------+ * The maximum subsequence sum for the first half is 6 (from :math:`a_0` to :math:`a_2`). * The maximum subsequence sum for the second half is 8 (from :math:`a_5` to :math:`a_6`). * The maximum subsequence in the first half that includes the last element is 4 (from :math:`a_0` to :math:`a_3`). * The maximum subsequence in the second half that includes the first element is 7 (from :math:`a_4` to :math:`a_6`). * Thus, the maximum subsequence that spans both halves and goes through the middle is :math:`4+7 = 11` (from :math:`a_0` to :math:`a_6`). .. admonition:: Activity :class: activity 1. Convince yourself that this algorithm works. 2. Create the function :code:`int maxSumRec( Vector a, int left, int right )` * The first is step is to define the base case. If there is one element :code:`left == right`. * Calculate the center * Calculate the max subsequence on the left side and right side. * Calculate the max subsequence that spans both halves. * Return the maximum between the three subsequences. 3. Analyze the running time. We can analyze the algorithm. * Let :math:`T(N)` be the time it takes to solve a maximum subsequence sum problem of size :math:`N`. * If :math:`N=1` (the base case), the program take some constant amount of time. * Otherwise the function performs two recursive calls. * It is done on a subproblems of size :math:`N`. * It takes :math:`T(N/2)`, for a total of :math:`2T(N/2)`. * Combining the two subsequences require two successive :code:`for` loops. * The work inside them is constant. * The amount of work is :math:`O(N)` * The total time is :math:`2T(N/2) + O(N)`. * it gives us the following equation: .. math:: \begin{cases} T(N) = 1, &\mbox{if } N=1 \\ T(N) = 2T(N/2) + O(N), &\mbox{otherwise } \end{cases} We need to express :math:`T(N)` in Big-Oh notation. We will see later how to do that precisely, but for now we just want a rough estimation. For now :math:`T(N) = 2T(N/2)+N`. * :math:`T(1) = 1` * :math:`T(2) = 4 = 2*2` * :math:`T(4) = 12 = 4*3` * :math:`T(8) = 32 = 8*4` The pattern is obvious, if :math:`N = 2^k`, then :math:`T(N) = N * (k+1) = N \log N+N = O(N \log N)`. We improved from :math:`O(n^3)` to :math:`O(N\log N)`! Achieving :math:`O(N)`! ----------------------- OK, now assume that we can achieve linear time complexity to calculate the maximum subsequence. What does it imply? * Maximum one :code:`for` loop. * Constant work in the loop. .. important:: Almost all linear algorithms have these limitations! .. admonition:: Activity :class: activity Can you find the logic behind this algorithm? This algorithm is a lot easier than the recursive algorithm and have better performance. .. warning:: In the examples, we never try to memorize what is the maximum subsequence. We only returned the value of the maximum subsequence. That's how we maintain a low complexity. The logic: * If :code:`a[i]` is negative, then it cannot be the start of the maximum subsequence. * Any negative subsequence cannot prefix the maximum subsequence. * If the subsequence between :code:`a[i]` to :code:`a[j]` is negative we can advance :code:`i`. * We can advance it to :code:`j+1`. * Consider :code:`p` any index between :code:`i+1` and :code:`j`. * Any subsequence starting a :code:`p` is not larger than the previous subsequence from :code:`a[i]` to :code:`a[p-1]`. * :code:`j` being the first index that causes the subsequence to in negative. * Thus advancing :code:`i` to :code:`j+1` is safe .. important:: The correctness is not obvious and would need to be proven. The corresponding function is simple: .. literalinclude:: ./AlgorithmAnalysis.java :language: java :linenos: :lines: 173-194 :caption: Algorithm 4 .. admonition:: Activity :class: activity Convince yourself that this algorithm works. Logarithms in the Running Time ============================== Below a linear running time, there is logarithm running time. The logarithm time usually appear around the general rule: An algorithm is :math:`O(\log N)` if it takes constant time (:math:`O(1)`) to cut the problem size by a **fraction** (often :math:`\frac{1}{2}`). .. important:: if constant time is required to reduce the problem by a constant amount (such as to make the problem smaller by 1), then the algorithm will be :math:`O(N)`. Only a special kind of problem can be :math:`O(\log N)`. If you have a problem with an input of size :math:`N`, then you will need :code:`O(N)` just to read the input. So :math:`O(\log N)` algorithms presume that the input is preread/preprocessed. I will just give one example: the binary search algorithm. Binary search Given an integer :math:`X` and a sorted array :math:`a` find :math:`i` such as :math:`a_i = X`. You should already know this algorithm so I will not spend a lot of time on it. The implementation is simple: .. literalinclude:: ./AlgorithmAnalysis.java :language: java :linenos: :lines: 196-218 :caption: Binary Search .. admonition:: Activity :class: activity 1. Convince yourself that the algorithm works. 2. Analyze the running time. Limitations of Worst-Case Analysis ================================== Sometimes the analysis is shown to be an overestimate. When it's the case, the analysis needs to be tightened. It may be that the average running time is significantly less than the worst-case running time and no improvement in the bound is possible. For many complicated algorithms, the worst-case happens very rarely. Calculating the average case is very complex (in many cases unsolved), and a worst-case bound is the best analytical result known.