Work Complexity - Examples
You should be able to derive the closed form of simple recursive equations which have
the form T(n) = a + b * n^{k} + 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(n^{2}) by deriving the closed form for
T and providing witnesses c and
n_{0}. Is T(n) also in O(n^{3})?
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.5n^{2} + 0.5n
= 0.5n^{2} + 2.5n +1
T(n) is in O(n^{2}) if c and
n_{0} exist such that for all n >= n_{0}
we have
0.5n^{2} + 2.5n +1 1 <= c * n^{2}
This holds for example for c = 2 and n_{0} = 2,
therefore T is in O(n^{2}). Note that there are
many possibilities for c and n_{0}, but we only
have to give one instatiation.
It is also in
O(n^{3}), since O-classes only give and upper
bound and every function that is in O(n^{2}) is also in O(n^{3}).
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(n^{2}).
Derive the timing function for palindrome (for the worst case) and provide witnesses
c and n_{0}. 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 T_{r}(n) = n
and T_{g} (n) = n to derive O(T_{p}).
- Base case, string is the empty string or string with exactly one character:
T_{p}(0) = 1
T_{p}(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:
T_{p}(n) = 4 + T_{r}(n-1) + T_{g}(n-1) + T_{p}(n-2)
= 4 + n - 1 + n - 1 + T_{p}(n-2)
= 2 + 2n + T_{p}(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.
T_{p}(0) = 1
T_{p}(2) = 1 + (2 + 2 * 2)
T_{p}(4) = 1 + (2 + 2 * 2) + (2 + 2 * 4)
.
.
.
T_{p}(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:
T_{p}(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 n^{2} + 2* n + 1
Now we have to find witnesses c and n_{0}. Since
0.5 n^{2} + 2* n + 1 <= 3n^{2}
for n >= 2, T_{p} is O(n^{2})
Remark:
- T_{r}: timing function for removeLast
- T_{g}: timing function for getLast
- T_{p}: 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 * n^{k}, we have to check whether c
is less, equal or greater than d^{k}
- T(n) = 2 * T(n/2) + n
- c = 2
- d = 2
- k = 1
- => c = d^{k} => 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 > d^{k} => T(n) = O
(n^{log22}) (which is ok as solution, but we
can simplify it since log_{2}2 = 1 to O(n)).
- T(n) = T(n/2) + b, b is a positive constant value
- c = 1
- d = 2
- k = 0
- => c = d^{k} => T(n) = O (log n)
Gabriele Keller
Last modified: Wed Oct 31 12:45:26 EST 2001