Algorithms

Analyze the worst-case running time for each of the following algorithms. You should give your answer in Big-Theta notation. You do not need to give an input which achieves your worst-case bound, but you should try to give as tight a bound as possible. In the column to the right of the code, indicate the cost of executing each line once. In the next column (all the way to the right), indicate the number of times each line is executed. Below the code, justify your answers (show your work), and compute the total runtime in terms of Big-Theta notation. You may assume that T(n) is the Big-Theta of the high-order term. You need not use Calculus techniques. However, you must show the calculations to determine the closed-form expression for a summation (represented with the symbol). You cannot simply say: Xie O(n), for instance. n i=1 In both columns, you don't have to put the exact values. For example, putting c for constant is fine. We will not be picky about off-by-one errors (i.e., the difference between n and n however, we will be picky about off-by-two errors (i.e., the difference between n and n 2). - 1); (a) Consider the following algorithm. | Cost | # times run 1 2 3 f(A[1, n]): ans = 0 for i = 1 to n-1: for j = i +1 ton: if A[i] > A[j]: ans += 1 4 5 6 7 8 return ans |