Work Complexity - Examples

You should be able to derive the closed form of simple recursive equations which have the form T(n) = a + b * nk + T(n-i) (for constant values i, a b), as in question 1 and 2. For more complex equations, you should be able to apply the table given in the lecture notes (sorting and complexity, page 5).

Question 1

Show that the function T(n), which is defined by the following two equations is in O(n2) by deriving the closed form for T and providing witnesses c and n0. Is T(n) also in O(n3)?

Solution 1

(read sum (i=1)(n) i as: the sum of all i from i = 1 to i = n)
   T (n) = 1 + sum (i=1)(n) (2 + i) 
         = 2 * n + 1 + (n+1)*n/2
         = 2n  + 1 + 0.5n2 + 0.5n 
         = 0.5n2 + 2.5n +1
T(n) is in O(n2) if c and n0 exist such that for all n >= n0 we have
    0.5n2 + 2.5n +1 1 <= c * n2
This holds for example for c = 2 and n0 = 2, therefore T is in O(n2). Note that there are many possibilities for c and n0, but we only have to give one instatiation. It is also in O(n3), since O-classes only give and upper bound and every function that is in O(n2) is also in O(n3).

Hint: if you find it hard to get from the recursive equation to the sum-form, look at example values for n. Usually, you can spot the pattern there:

Question 2

Consider the following naive implementation of a function which checks if a word is a palindrome (that is, a string which reads the same backwards and forwards).
palindrome:: String -> Bool
palindrome ""     = True
palindrome [c]    = True
palindrome (c:cs) 
  | c == getLast cs = palindrome (removeLast cs) 
  | otherwise       = False
The functions getLast (which returns the last char of a non-empty string) and removeLast (which deletes the last char of a string) are O(n), where n is the length of the string. Show that under this assumption, palindrome is O(n2).

Derive the timing function for palindrome (for the worst case) and provide witnesses c and n0. Assume the string has an even number of characters (this does not affect the result, but it simplifies the derivation).

Solution 2

Since the two auxiliary functions are O(n), we can approximate their timing function with Tr(n) = n and Tg (n) = n to derive O(Tp). Remark:

Question 3

Find the O-classes of the following recursively defined functions (the values for the base cases are not relevant). Hint: use the table on page 5 in the lecture notes on sorting and complexity.

Solution 3

We have to determine which of the five patterns given in the table applies in each case. Since all equations have the form T(n) = c * T(n/d) + b * nk, we have to check whether c is less, equal or greater than dk
Gabriele Keller
Last modified: Wed Oct 31 12:45:26 EST 2001