Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Tutorial 1
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?
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 )
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?
1