Running Time Analysis PDF

# 7. Running Time ## 7.1 Fundamentals of running time We want our algorithms to be as fast as possible and consume as little memory as possible. Sometimes, these are conflicting goals. In this unit, we focus on the running time of algorithms - many concepts also apply to the memory consumption....

# 7. Running Time ## 7.1 Fundamentals of running time We want our algorithms to be as fast as possible and consume as little memory as possible. Sometimes, these are conflicting goals. In this unit, we focus on the running time of algorithms - many concepts also apply to the memory consumption. The first problem we have is to clearly say what it means to have a fast algorithm. The speed should be independent of the current machine, since different machines may lead to different execution times. Hence, we need a general machine-independent formalism to analyse our algorithms. The solution is, to consider the running time of an algorithm as a function, that assigns the input size to the number of the used elementary operations. Examples for typical input sizes are: * number of elements * size of a list * number of binary digits of a number Examples for typical elementary operations are: * comparisons * arithmetic or boolean operations * assignments For simplicity, we usually do not focus on all primitive operations. Instead, we focus on the operation that occurs most frequently. Later, when working with asymptotic running times we can see that this restriction is not a problem. ## 7.1.1 Worst Case Analysis In the worst case analysis we try to find the best possible function for the worst input, i.e., we are looking for a function that never underestimates the runtime behaviour for all possible inputs. Let us be more precise. Thus, let __A__ be an algorithm and let __I__ be an input for this algorithm. Then __TA(I)__ is the running time of the algorithm for the input __I__. The worst case running time __TA(n)__ is now defined as: $TA(n) = max_{input I} TA(I)$. ## 7.1.1 Linear search Let us discuss the worst case analysis by considering the linear search algorithm, we use _ALS_ as abbreviation. Recall that the linear search algorithm gets as input a list of elements _xs_ and an element _k_ (the input _I_) and it returns the index of _k_ in _xs_, if possible. Here, the input size _I_ is the length of _xs_ we ignore _k_ for the input size since only the length of _xs_ can differ. Moreover, _TLS(I)_ counts the number of comparisons of _k_ with an element in _xs_. Next, consider the example I =([3,1,5,2,4], 1). Then, we have _TLS(I)=2_, since two comparisons are needed to the element 1 in the list. However, _TLS(5)=5_, since in the worst case we need 5 comparisons to find an element _k_ in a list of 5 elements - this happens if _k_ is not in the list or the last element of the list. Finally, we can say that _TLS(n)=n_, since in the worst case we need _n_ comparisons to find an element in a list of _n_ elements. No matter how the input _I_ looks like, we can always conclude that _TLS(I) ≤ n_ - this is the nature of worst case analysis. **Attention:** In this subsection we used the notations _TA(I)_ and _TA(n)_. From now on, we will omit the index __A__, if the context is clear. Moreover, when making the worst case analysis, we will not use the notation _T(I)_, instead we only focus on _T(n)_. Thus, _T(n)_ is the worst case running time of the mentioned algorithm with input size _n_. ## 7.1.2 Cartesian Product Let us consider another example. The following algorithm computes the cartesian product of two input lists _xs_ and _ys_: ```python def cart_product(xs, ys): prod = [] for x in xs: for y in ys: prod.append((x,y)) return prod ``` Here, the input size is the number _n_ of elements of _xs_ and the number _m_ of elements in _ys_. The running time function counts the number of _append(-)_ calls. The function goes through all elements of _xs_ and for each of these elements it executes the inner loop for each element in _ys_. Each call of the inner loop leads to _m_ calls of _(*)_. Since the the inner loop is executed exactly _n_ times, the _append(-)_ function is called exactly _nm_ times. Hence, the worst case running time is _T(n,m) = n.m_. ## 7.1.3 Binary Search In the third unit we discussed the binary search algorithm: ```python def binary_search(xs, k): n = len(xs) def bin_search(left, right): if left > right: return n m_pos = (left + right) // 2 m = xs[m_pos] if k == m: return m_pos elif k < m: return bin_search(left, m_pos) else: return bin_search(m_pos+1, right) return bin_search(0, n) ``` Moreover, we already analysed the number of steps, the binary search function uses for a list of input size _n_ and concluded _log2(n)_. However, this is half the truth. In each step we have in the worst case three comparisons and two assignments, culminating in _5.log2(n)_ operations for the recursive calls. Finally, _n = len(xs)_ is another assignment. Therefore, the running time of the binary search algorithm is in the worst case exactly _T(n) = 5.log2(n) + 1_. This makes our world a bit more complicated, since this function is not as easy as _n_ or _nm_. To simplify our running time functions, we will use the so called asymptotic running time. ## 7.2 O-Notation As we have seen in the last section, the running time function can look very complicated. To solve this problem, we will us O-Notation, to concentrate on the essence of such a function. For the asymptotic running time we first compute _T(n)_ and secondly classify _T(n)_ according to the O-Notation The main advantage of this approach can be seen when looking back to the cartesian product algorithm. Here, we simply ignored, that the _for-loop_ also takes time to extract the elements from the list - we only considered the _append(-)_ calls. In our lecture, we consider the O-Notation only briefly. Let _f: No R+_ be a function, we say that _O(f(n))_ is the set of all functions _g(n)_ having _f(n)_ as an asymptotic upper bound¹ - we write _g(n) ∈ O(f(n))_. According to this, similar running times are combined to run time classes. For our purposes, the following three rules are sufficient: (i) We ignore constant factors, e.g., _5.log(n) ∈ O(log2(n))_ (ii) We ignore smaller summands, e.g., _log2(n) + 1 ∈ O(log(n))_ _3.mn ∈ O(mn)_ _n + log2(n) ∈ O(n)_ (iii) The O-Notation gives an upper bound, e.g., _log2(n) ∈ O(n)_ _n ∈ O(n²)_ **Attention:** For the sake of readability, we remove the base of the logarithm, i.e., whenever we write _log(n)_ we assume the basis to be 2. Moreover, we sometimes omit the brackets around _n_ when applying the log-function. This shall improve the readability as well. Example: We write _logn ∈ O(n)_ instead of _log2(n) ∈ O(n)_. ## 7.2.1 Hierarchy of run time classes The following is an ordered list of typical run time classes. * O(1) constant running time, e.g., accessing an element * O(logn) logarithmic running time, e.g., binary search * O(√N), e.g., prime test * O(n) linear running time, e.g. linear search or finding the minimum/maximum of an unsorted list * O(nlogn) near-linear running time, e.g., Mergesort or Heapsort (which we consider later) * O(n²) quadratic running time, e.g., _Insertionsort_, _Selectionsort_, considering all pairs of elements of a list * O(n³) cubic running time, e.g., solving linear equations, considering all triple of elements of a list * O(n) polynomial running time, i.e., in computer science this is considered as efficient * O(2n) exponential running time, i.e., considering all subsets * O(n!) factorial running time, i.e., considering all permutations ## 7.3 Analysis of sorting algorithms For the sorting algorithms we always consider the input size _n_ to be the number of elements of the list. Moreover, we will count the number of comparisons between elements of the list. Hence, _T(n)_ will be the worst case number of comparisons for lists of _n_ elements. ## 7.4 Bounds for algorithmic problems In the former sections, we successfully derived worst case running times of different sorting algorithms and concluded that among the algorithms we know yet, _mergesort_ is the best, since its worst case running time is _O(nlogn)_. But maybe there are faster algorithms, algorithms we do not know yet. This raises the question of the complexity of algorithmic problems. Let _P_ be an algorithmic problem. ### Upper bound for P If there is an algorithm _A_, that solves _P_ in time _T(n)_, then _T(n)_ is an upper for the complexity of the algorithmic problem _P_. Here are some examples: (i) If we consider the search problem, then we know that linear search solves this problem and has running time _T(n) = n_. Hence, n is an upper bound for the search problem. (ii) If we consider the sorting problem, we know that _selectionsort_ solves this problem and has running time _T(n) ∈ O(n²)_. Hence, _O(n²)_ is an upper bound for the sorting problem. However, _mergesort_ is faster and still solves the sorting problem. Thus, _O(nlogn)_ is another (better) upper bound for the sorting problem. ### Lower bound for P If there is no algorithm solving _P_ that is faster than _f(n)_, than _f(n)_ is a lower bound for the complexity of the algorithmic problem _P_. Here are some examples: (i) If we consider the search problem, then no algorithm has less than _n_ comparisons, since the value that has to be found might be at the last accessed position of the list. (ii) For the sorting problem we can find a similar argument. Each element has to be accessed at least once and used for at least one comparison. Therefore, we cannot have less than _n/2_ comparisons. However, between _n/2_ and _nlogn_, there is still a gap, we would like to close. **Attention:** Finding upper bounds for algorithmic problems is easy, since it suffices to develop one algorithm whose running time fits to this upper bound. In contrast to that, finding lower bounds for algorithmic problems is much harder, since we have to argue about the running times of all algorithms - including those we do not know. ## 7.4.1 Decision trees Our objective is to find a better lower bound for comparison based sorting algorithms. For this, we need the concept of decision trees. Let _A_ be an arbitrary comparison based algorithm, i.e., the behaviour of _A_ with input sequence _X = [x1,..., xn]_ depends solely on the results between elements of _X_. A general decision tree for _A_ then might look like this: The decision tree consists of inner nodes, each inner node contains a comparison of two elements and two outgoing edges (yes/no) to the next nodes. The highest node is called root. At the bottom of the tree we have the leafs, they include the possible outputs of the algorithm. The length of a longest path from the root to a leaf is called height of the tree. This height is a lower bound for the worst case running time of _A_. The decision tree in the example above has height 3, since a longest path from the root „Y₁ < Y2" to a leaf (for example to Y2) has three edges. Without any proof, we have the following lemma: **Lemma 2:** A decision tree with _m_ leafs has height at least _logm_. ## 7.4.2 Comparison based Sorting Using the concept of decision trees, we can now proof our main theorem. **Theorem 1:** Let _A_ be any comparison based sorting algorithm. Then _A_ needs at most _½(logn - 1)_ comparisons. **Proof:** First of all, we know that the output of a sorting algorithm has to be a permutation of the input list. Next, we know that the number of possible permutations of a general list is exactly _n!_. Hence, the decision tree of _A_ must have at least _n!_ leafs. By our lemma, we know that the decision tree must have height at least _log(n!)_ and since the height of the decision tree is a lower bound for the running time of _A_, we can conclude _TA(n) ≥ log (n!)_. Thus, every comparison based sorting algorithm has running time at least _log(n!)_. Finally, we have to find a lower bound for _log(n!)_. For this, we can estimate $n! = 1\cdot 2 \cdots \frac{n}{2} \cdot(\frac{n}{2} +1) \cdots (n-1) \cdot n$ and obtain our final result $TA(n) = log (n!) ≥ log ((\frac{n}{2})^\frac{n}{2}) = \frac {n}{2} log (\frac{n}{2}) = \frac{n}{2}(logn - log2) = \frac {n}{2}(logn -1)$ as desired. **Attention:** There are sorting algorithms that can under certain circumstances sort faster than _n logn_. However, these algorithms are not comparison based. They use other techniques and usually, they are only restricted to specific types of elements.