Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Tutorial 1 (Model Answer)
1. Using asymptotic notation, state an upper and lower bound for the time complexity of
the SimpleSearch procedure for any input. Can you also give a tight (Θ) bound?
Answer: Although asymptotic notation applies to functions, in computing it is also
(abusively) applied to algorithm performance even when the performance cannot be
characterised by a single function. So, we say that the time complexity of the algorithm
for any input has an upper bound O(g(N)) if its worst case running time is O(g(N)),
and has a lower bound Ω(g(N)) if its best case running time is Ω(g(N)).
Since the time taken by simple search in the worst case is aN + b, the algorithm never
takes more time than this for any input, so the upper bound is O(N).
The best case for simple search is that k is the first element of the sequence. This is
down to luck, but it is still possible for the algorithm to finish after checking just this
one element. The time taken in this case is independent of the length of the sequence,
so it is constant for all N. Let’s call it c. This possibility still exists for any input, so
the lower bound is Ω(1).
In order to give a tight bound, there now does have to be a single function g(N)
that provides both an upper and a lower bound for the running time of the algo-
rithm (within a constant factor). If you are considering a single case, like worst case,
then this will be possible. If you are considering any input, it does not always ex-
ist. In this case, since the time complexity has different upper and lower bounds
there is no tight bound. Neither T (N) = Θ(N) nor T (N) = Θ(1) are correct.
2. (Cormen Exercise 3.1-4). The formal definition of O is:
O(g(N)) =
{
f(N) | there are positive constants c and N0
such that 0 ≤ f(N) ≤ c g(N) for all N ≥ N0
}
.
Using this definition, show whether each of the following statements is true or false.
(a) 2N+1 = O(2N )
(b) 22N = O(2N )
1
Answer: (a) is true. Instantiating the set condition, we need to show that there are
positive c and N0 such that the inequalities 0 ≤ 2N+1 ≤ c2N are true for all N ≥ N0.
Firstly, 2N+1 ≥ 0, for all N , so this is true for all N greater than any N0. Next, we
need to solve c2N ≥ 2N+1 for c:
c2N ≥ 2N+1 , so (since 2N is positive)
c ≥
2N+1
2N
, and so
c ≥ 2.
So, c2N ≥ 2N+1 ≥ 0 when c ≥ 2, for all N . So, for say c = 2 and N0 = 1, the O(2N )
condition is true. Therefore, such a c and N0 exist and (a) is true.
(b) is false. We need to show that there are positive c and N0 such that 0 ≤ 22N ≤ c2N
for all N ≥ N0. As before, 22N ≥ 0, for all N . Now, solving c2N ≥ 22N for c:
c ∗ 2N ≥ 22N , so
c ≥
22N
2N
, and
c ≥ 2N .
There are no constants c and N0 such that c ≥ 2N for all N ≥ N0.
3. If a0 and a1 are constants, and a2 is a positive constant, show that a2N
2 + a1N + a0 is
not in O(N). What are the consequences for algorithm design? What are the limitations
of these consequences?
Answer: Instantiating the O(N) set condition, we need to show that there are
positive c and N0 such that the inequalities 0 ≤ a2N2 + a1N + a0 ≤ cN are true for
all N ≥ N0. We expect the second inequality to fail, so we will start there. We need
to solve a2N
2 + a1N + a0 ≤ cN for c:
cN ≥ a2N2 + a1N + a0 , iff (since N is positive)
c ≥ a2N + a1 +
a0
N
. 1 mark
Now
lim
N→∞
a2N =∞ , and
lim
N→∞
a1 = a1 , and
lim
N→∞
a0
N
= 0 .
So
lim
N→∞
(a2N + a1 +
a0
N
) =∞+ a1 + 0 =∞, 1 mark
2
and so there are no c and N0 that satisfy the set condition.
In terms of algorithm design, this means that any algorithm with a time complexity
that has an N2 term will take longer than any algorithm whose time complexity has
a highest order term aN , when N is sufficiently large. So, if the best algorithm we
have has N2 time complexity, then we know that it is worth trying to find a “linear
algorithm”, because it should be a faster solution.
The limitation is what the exact value of “large N” turns out to be. (i.e. N0 in the
definition of O.) Depending on the constants involved, the size of the input for which
the O(N) algorithm becomes faster might be impractically large. It must become
faster for some N , but if this N is larger than the largest input you are going to need
to handle, or simply larger than the average input, it will be of no use.
3