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 O(k).

B. Derive the cost function for the algorithm.

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).

Satisfies is shown below:

input: k output: S[k] a 1D int array representing a satisfying assignment for F S = array[k] // int array, initialized to all 0s, carry = 0 // integer number of variables FUm] [3] // an m x 3 2D array encoding a formula (m in 0(k")) // each element will store a 0 or a 1 while carry - 0 and not satisfies (S,F) // satisfies) is from Question 3 carry1 for i - 0 k c-(Si] + carry)2 s[1] = (s[i] carry C + carry) % 2 return carry- 0 Note: This is a hard problem. Hint: Suppose satisfies) always returns false. The number of iterations by the while loop depends strictly on the carry variable. I recommend running some examples by hand for n = 1,2,3,4 input: S[k] output: true if and only if formula F is satisfied by assignment S for i -0. ..m // a 1D array of size k, encoding a variable assignment Formula F[n] [3] // an m x 3 2D array encoding a formula (m in 0(k")) clause false for j 0... 3 if F[i] [jl