Palindrome Checker

A palindrome is a word or phrase that reads the same both forward and backward. Some examples include racecar, kayak, and deified.

Here’s a function that determines whether a string is a palindrome:

	def is_palindrome(string):

	left_index = 0
	right_index = len(string) - 1

	# Iterate until left_index reaches the middle of the array:
	while left_index < len(string) // 2:

	# If the character on the left doesn't equal the character
	# on the right, the string is not a palindrome:
	if (string[left_index] != string[right_index]):
	return False

	left_index += 1
	right_index -= 1

	# If we got through the entire loop without finding any
	# mismatches, the string must be a palindrome:
	return True

Let’s determine the Big O of this algorithm.

In this case, N is the size of the string passed to this function.

The guts of the algorithm takes place within the while loop. Now, this loop is somewhat interesting because it only runs until it reaches the midpoint of the string. That would mean that the loop runs N / 2 steps.

However, Big O ignores constants. Because of this, we drop the division by 2, and our algorithm is O(N).