A Guide to Algorithm Design

8 Chapter 1. Introduction to complexity

somewhere else, then we have an exhaustive method that always performs

the minimum number of operations. However, this method clearly takes an

exponential amount of time, and thus is not satisfying. In fact, to the best

of our knowledge, the complexity of the problem is still open. There is a

common misbelief that the problem of determining whether there exists an

addition chain whose length does not exceed some bound is NP-complete. In

fact, the result is known to be NP-complete only for a sequence of integers

n

1

, n

2

, . . . , n

m

, but not for a single value n [32].

1.2 Asymptotic notations: O, o, Θ, and Ω

Let