Question

Determine the worst-case complexity in terms of comparisons of the algorithm from Exercise 9 in Section 3.1 for determining whether a string of n characters is a palindrome.

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result of previous exercise:

Procedure: palindrome $(a_1,a_2,...a_n:integerswithn\ge 1)$.

$$\begin{gathered} k:=True \\ fori:=1to\left|\frac{n}{2}\right| \end{gathered}$$

if $a_i\ne a_{n-i+1}thenk:=False$

return k.

Solution

The algorithm makes 1 comparison in each iteration of the for-loop $(a_i\ne a_{n-i+1})$

Since i can take on the values from 1 to $\left|\frac{n}{2}\right|$(for $i:=1to\left|\frac{n}{2}\right|$), i can take on $\left|\frac{n}{2}\right|$values and thus there are $\left|\frac{n}{2}\right|$iterations of the for-loop.

The number of comparisons is then the product of the number of iterations and the number of comparisons per iteration.

Number of comparisons $\left|\frac{n}{2}\right|·1=\left|\frac{n}{2}\right|$

Thus $\left|\frac{n}{2}\right|$comparisons are made and $\left|\frac{n}{2}\right|$ is O(n) .