For a sequence of n integers in range [-2 … n-2], and considering worst-case time complexity, which sorting algorithm(s) can be optimally implemented to guarantee a linear time to sort this sequence? 

Solve, in big-θ, the following recurrence relation

T(n) = 4 * T(n/4) + c, where n >= 4
T(n) = b, where n = 1

for constants b and c.

Given the following pseudocode, derive the recurrence relation that represents its time complexity. 

def fibonacci(n):
    if (n==0 or n==1):
        return n 
    return fibonacci(n - 1) + fibonacci(n - 2)

Let b and c represent constant values. What is the base case and recurrence step?  

What is the auxiliary space of least significant digit (LSD) radix sort for an array of n integers? 

Consider the following Python code that returns true if and only if the string s is a palindrome. A string is a palindrome if it is the same when reversed, e.g., "madam" is a palindrome whereas "algorithm" is not. 

What is an appropriate loop invariant for this algorithm at the point specified?

Which of those sorting algorithms has time complexity that is independent from the array contents (assuming that it is an array of integers)?

Consider the following algorithm, which returns the index of the maximum value in an array of integers.

The function accepts a list A[1…n] with n items

myfunc(A, n):
    i = 1
    j = n
    while (i < j):
        if (A[i] > A[j]):
            j = j – 1
        else:
            i = i + 1
        ### Loop Invariant ###
    return i

What is an appropriate loop invariant for this algorithm at the point specified?

Consider the following algorithm, which accepts a list A[1…n] with n items and performs a set of operations:

myfunc(A, n):
    i = 1
    while (i < n):
        ### Loop Invariant ###
        if (A[i] > A[i+1]):
            temp = A[i]
            A[i] = A[i+1]
            A[i+1] = temp
        i = i + 1  
    return A[n]

What is an appropriate loop invariant for this algorithm at the point specified?

Solve, in big-θ, the following recurrence relation

T(n) = 2 * T(n/2), where n > 1
T(n) = c, where n = 1
for a constant c.

Given the following pseudocode, derive the recurrence relation that represents its time complexity. 

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)

Let b and c represent constant values. What is the base case and recurrence step?