A palindrome is a word that reads the same forwards and backwards. Both algorithms below check whether a word is a palindrome. Characters are indexed from 0.
Algorithm A
word ← USERINPUT
n ← LEN(word)
mismatches ← 0
FOR i ← 0 TO n - 1
IF word[i] ≠ word[n - 1 - i] THEN
mismatches ← mismatches + 1
ENDIF
ENDFOR
IF mismatches = 0 THEN
OUTPUT 'Palindrome'
ELSE
OUTPUT 'Not a palindrome'
ENDIF
Algorithm B
word ← USERINPUT
left ← 0
right ← LEN(word) - 1
same ← True
WHILE left < right AND same = True
IF word[left] ≠ word[right] THEN
same ← False
ENDIF
left ← left + 1
right ← right - 1
ENDWHILE
IF same = True THEN
OUTPUT 'Palindrome'
ELSE
OUTPUT 'Not a palindrome'
ENDIF
The user enters racecar. State how many times two characters are compared (≠) in each algorithm. Give two reasons why Algorithm B is more time efficient.
Model answer
Algorithm A: 7 comparisons
Algorithm B: 3 comparisons
Reason 1: B works in from both ends and stops at the middle, so it compares each pair of characters only once, whereas A compares every pair twice.
Reason 2: B stops as soon as it finds a pair that does not match, whereas A always checks every character.
Explanation
racecar has 7 letters, so A's FOR loop makes 7 comparisons; B compares r/r, a/a and c/c, and then left and right meet at the middle e. For a word such as robots, B stops after its first comparison (r and s do not match) while A still makes 6. The two reasons are different ideas: halving the comparisons, and stopping early.