In the following procedure, the input is an array A[1..n] of arbitrary integers, A.size is a variable containing the size n of the array A (assume that A contains at least n > 2 elements), and “return” means return from the procedure call. 0. Procedure nothing(A) 1. A[1] := 0 2. A[2] := 1 3. for i = 3 to A.size do 4. s := 0 5. for j = 1 to i-1 do s := s + A[j] 6. if A[i] is not equal to s then return 7. return QU. Let T(n) be the worst-case time complexity of executing procedure nothing() on an array A of size n > 2. Assume that assignments, comparisons and arithmetic operations, like additions, take a constant amount of time each.
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
---|---|---|---|---|---|---|
29 | 30 | 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 | 1 | 2 |