example 1: Time complexity analysis of SequentialSearch ------------------------------------------------------- SeqSearch returns true if x is in A[1..n] and false otherwise: SeqSearch(A[1..n],x) i := 1 found := false while i <= n and not found do if A[i] = x then found := true end if i := i+1 end while return found Let T(n) be the worst-case time complexity of the Sequential Search (SS) algorithm (the sequential search of an item x in an array of size n). Question: Show that T(n) is Omega(n) Upper bound: show that T(n) is O(n) --------------------------------------- For every n, and EVERY input of size n, the following is true: 1) The while loop is executed at most n times - i is incremented on each iteration, so i > n after n iterations 2) Each iteration takes c steps for some constant c. - the details about what counts as a step doesn't matter. 3) d steps are taken outside the loop, for some constant d Therefore: for **ALL** inputs of size n, the time needed for the entire algorithm is **at most** cn+d So the worst case time complexity of the algorithm T(n) is O(n). Lower bound: show that T(n) is Omega(n) ------------------------------------------ Aside: for every n, there are inputs of size n, where the algorithm is very fast (takes very few steps). i.e., suppose x is at index A[1] (or A[15], for that matter). -> the while loop is executed only once (or 15 times), since the loop terminates after x is found. -> The body of the loop takes c steps, for some constant c. The time needed FOR THIS INPUT is **at least** c (or 15c). Therefore the worst-case time complexity of SeqSearch is Omega(1). Is this true? Yes, but very weak. (For full marks), we want to find the strongest result possible. We want to show that T(n) is Omega(n): To prove this, for every n, we find a "bad" input of size n that will cause the algorithm to take at least cn steps (for some constant c). Note: We can't prove that this **is** the worst-case input, but we can show that it is a "bad" input. A bad input is when the first appearence of x in A is in A[n]. (i.e., A[n]=x and A[i] \ne x for all i s.t. 1 <= i < n). For every n, and THIS input of size n, the following is true: -the while loop is executed n times, -each iteration takes at least c steps (for some constant c), So, for this input the algorithm executes at least cn steps. Therefore: for **ONE** input of size n, the time needed for the entire algorithm is **at least** cn So the worst-case time complexity of the algorithm is Omega(n). Since the w.c. time complexity of the algorithm T(n) is both O(n) and Omega(n), it is Theta(n). * * * * * * * * Now, consider an input where the first instance of x is the "middle" element of A (i.e, A[n/2]=x and A[i] \ne x for all i s.t. 1 <= i < n/2 --- for simplicity we assume that n is even, if not we would take floor(n/2) instead of n/2). In this case the loop is executed n/2 times, and each iteration takes at least c steps for some constant c. So for this input the entire algorithm requires at least (c/2)n steps. So on the basis of this input as well, the worst case time complexity ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ of the algorithm is Omega(n). The same conclusion would be drawn for an input where the first occurence of x in A is in position n/100. ------------------------------------------------------------------------- ------------------------------------------------------------------------- Example 2: Time complexity analysis of Bubblesort ------------------------------------------------- BubbleSort(A[1..n]) last := n sorted := false while not sorted do sorted := true for j := 1 to last-1 do if A[j] > A[j+1] then swap A[j] and A[j+1] sorted := false end if end for last := last-1 end while How does bubblesort work? At the end of the i-th iteration of the while loop, A[last+1..n] contains in sorted order the i largest elements of A. 10 5 9 8 6 j=1: 5 9 8 6 10 j=2: 5 8 6 9 10 j=3: 5 6 8 9 10 j=4: 5 6 8 9 10 Let T(n) be the worst-case time complexity of the BubbleSort (BBS) algorithm. Question: Show that T(n) is Omega(n^2). Upper bound: show that T(n) is O(n^2). ----------------------------------------- For every n, and for EVERY input of size n the following is true: 1) While loop is executed at most n-1 times. Each time "last" is reduced by 1. -> after n-1 iterations, last=1 -> no iterations of the for loop are performed on iteration n-1 -> "sorted" is true on iteration n-1 -> while loop ends on iteration n-1 (if not earlier) 2) Each iteration of the while loop takes at most cn time, for some constant c -for loop excutes at most n-1 times, since "last" is always at most n. 3) d steps are taken outside the while loop, for some constant d Therefore: for **ALL** inputs of size n, the time needed for the entire algorithm is **at most** cn(n-1) + d So the worst case time complexity of the algorithm T(n) is O(n^2). Lower bound: show Omega(n^2). --------------------------------------------------------------- Aside: T(n) is Omega(n) For every n, there are inputs of size n for which the algorithm is very fast (takes very few steps). i.e., suppose the input array A (of size n) is already sorted. -the while loop is executed only once. -the body of the while loop takes at least c(n-1) time, for some constant c (because the for loop is executed n-1 times). Therefore: for **ONE** input of size n, the time needed for the entire algorithm is **at least** c(n-1). So the worst-case time complexity of BubbleSort T(n) is Omega(n). This is true, but it is a very weak statement. (not worth full marks) ----- Now we show, the worst-case time complexity of BubbleSort is Omega(n^2). To prove this, for every n we have to identify a "bad" input (not the worst-case input!!) of size n that will cause the algorithm to take at least cn^2 steps (for some constant c). Such a bad input is when the input array A is in reverse sorted order. For every n, and THIS input of size n, the following is true: * After one iteration of the while loop, the largest element is in A[n] and the rest of the array A[1..n-1] is in reverse sorted order. This iteration of the while loop requires at least n-1 steps (because the inner for loop is is executed n-1 times). * After two iterations of the while loop, the largest two elements are sorted in A[n-1..n] and the rest of the array A[1..n-2] is in reverse sorted order. This iteration of the while loop requires at least n-2 steps (because the inner for loop is is executed n-2 times). . . . * After n-1 iterations of the while loop, the largest n-1 elements are sorted in A[2..n] and the rest of the array A[1] is in reverse sorted order. (So now the array is sorted.) This iteration of the while loop requires at least 1 step (because the inner for loop is is executed 1 time). So, for this input the while loop requires the execution of at least (n-1) + (n-2) + ... + 1 = (n-2)(n-1)/2 steps Therefore: for **ONE** input of size n, the time needed for the entire algorithm is **at least** (n^2 -3n +2)/2 So the worst-case time complexity of the algorithm is Omega(n^2). Since the w.c. time complexity of BubbleSort is both O(n^2) and Omega(n^2), it is Theta(n^2).