The following algorithm

• takes a sorted array A[1..n] of characters, and
• outputs, in reverse order, all 2-letter words νω such that ν ≤ ω.

Count the number of primitive operations (evaluating an expression, indexing into an array). What is the time complexity of this algorithm in big-O notation?

for all i = n down to 1 do
    for all j = n down to i do
        print A[i] A[j]
    end for
end for

This totals to \( 2n^2+5n+1 \), which is \( O(n^2) \)

Develop an algorithm to determine if a character array of length n encodes a palindrome — that is, it reads the same forward and backward. For example, racecar is a palindrome.

1. Write the algorithm in pseudocode.

2. Analyse the time complexity of your algorithm.

3. Implement your algorithm in C. Your program should accept a single command line argument, and check whether it is a palindrome. Examples of the program executing are

   ./palindrome racecar
   yes
   ./palindrome reviewer
   no
   

   Hint: You may use the standard library function strlen(3), which has prototype size_t strlen(char *), is defined in <string.h>, and which computes the length of a string (without counting its terminating '\0'-character).

isPalindrome(A):
    Input  array A[0..n-1] of chars
    Output true if A palindrome, false otherwise

    i = 0; j = n-1
    while i < j do
        if A[i] ≠ A[j] then
            return false
        end if
        i = i + 1; j = j - 1
    end while

    return true

Time complexity analysis: There are at most \( \lfloor n/2 \rfloor \) iterations of the loop, and the operations inside the loop are \( O(1) \). Hence, this algorithm takes \( O(n) \) time.