Consider the worst-case scenario and for each questions: Feel free to use O(1) instead of specific constants when analyzing the algorithms a. State the size of the input in big-Oh. For example, if the input to an algorithm is an array of size k, then the input size is n E O(K) b. Derive the cost function for the algorithm. Be sure to show your work c. State the complexity of the algorithm in Big-Oh. The complexity MUST be stated in terms of input-size d. Prove that the derived cost function is in the stated order (big-Oh) Sample answers are given below in red: Example 1: input: M[k] [k] // A matrix (2D array) of size k x lk output: M x V Rarray [k new array of size n [2] for j -0 k Example 2: class List: class Node V[k] // A vector (1D array) of size k next // next pointer elem // data stored in node head tail size // pointer to head of list // pointer to tail of list // size of list 2[n] kIn n) input: L :Linked List output: if the 1ist is a palindrome for i- 0 . . k startL.head n = List, size for i 0 n 2 [2] I/ [1] is also fine here [2] I/ [1] is also fine here n/2] [n/2] [n-2i-1] return R curr start 1. From neO(K2+K), we get neO(K2) 2. See beside code 3. 9n2 3n +2 4.9n23n +21: match = true for j = 0 k t-s 2 match-false break if match return i else return-1 break return H input: Positive integer n> 1, positive integer p>1 output: returns true if n is a power of p input: P[k] I/ Array of (x,y) coordinates output: d I Maximum distance over all pairs of coordinates while n % ( q*q)--0 q=q*q for i=0 k-1 while qp for j -i+1 k d max (d, sqrt(dx*dx dy*dy)) = + q - sqrt(q) return d return n # 1 Hint: Treat the integer as a sequence of bits Recall than an integer n requires at minimum log(n) bits