# 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
• T (0) = 1
• T (n) = 2 + n + T(n-1)
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:

• T(0) = 1
• T(1) = (2 + 1) + 1
• T(2) = (2 + 2) + (2 + 1) + 1
• T(3) = (2 + 3) + (2 + 2) + (2 + 1) + 1
• T(4) = (2 + 4) + (2 + 3) + (2 + 2) + (2 + 1) + 1
• T(n) = (2 + n) + (2 + n-1).. .. + (2 + 1) + 1
• => T(n) = 1 + sum (i=1)(n) (2 + i)

#### 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).
• Base case, string is the empty string or string with exactly one character:
```Tp(0) = 1
Tp(1) = 1```
• String has n characters: function application of getLast, removeLast, and palindrome and ==, plus the cost of palindrome on a string of n-2 characters (first and last of argument string removed), removeLast and getLast on a string of n-1 characters:
```Tp(n) = 4 + Tr(n-1) + Tg(n-1) + Tp(n-2)
= 4 + n - 1 + n - 1 + Tp(n-2)
= 2 + 2n  + Tp(n-2)
```
We assume (see question) that the string has an even number of characters. Since the size of the string is decremented by 2 in each call until there are only 0 or 1 characters left, so we have n/2 recursive calls.
```Tp(0) = 1
Tp(2) = 1 + (2 + 2 * 2)
Tp(4) = 1 + (2 + 2 * 2) + (2 + 2 * 4)
.
.
.
Tp(n) = 1 + (2 + 2 * 2) + (2 + 2 * 4) +  (2 + 2 * 6) +  (2 + 2 * 8) + ... (2 + 2 *( n - 2)) + (2 + 2 * n)
```
Or, written as a sum:
```Tp(n) = 1 + sum (i=1)(n/2) (2 + 2 * (2 * i))
= 1 + sum (i=1)(n/2) (2 + 4 * i)
= 1 + 2 * (n/2) + 4 * sum (i=1)(n/2) i
= 1 + n + 4 * ((n/2)* (n/2 +1) / 2)
= 1 + n + n * (n/2 +1)
= 0.5 n2 + 2* n + 1
Now we have to find witnesses c and n0. Since
0.5 n2 + 2* n + 1  <= 3n2

for n >= 2, Tp is O(n2)
```
Remark:
• Tr: timing function for removeLast
• Tg: timing function for getLast
• Tp: timing function for palindrome

#### 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.
• T(n) = 2 * T(n/2) + n
• T(n) = 2 * T(n/2) + b, b is a positive constant value
• T(n) = T(n/2) + b, b is a positive constant value

#### 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
• T(n) = 2 * T(n/2) + n
• c = 2
• d = 2
• k = 1
• => c = dk => T(n) = O (n * log n)
• T(n) = 2 * T(n/2) + b, b is a positive constant value
• c = 2
• d = 2
• k = 0
• => c > dk => T(n) = O (nlog22) (which is ok as solution, but we can simplify it since log22 = 1 to O(n)).
• T(n) = T(n/2) + b, b is a positive constant value
• c = 1
• d = 2
• k = 0
• => c = dk => T(n) = O (log n)

Gabriele Keller