程序代写代做代考 algorithm Imperial College London – Department of Computing

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