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
Last modified: Wed Oct 31 12:45:26 EST 2001