(a) (3 points) Construct P and S such that i > n m on termination. Show your work.

(b) (2 points) What is a best-case runtime scenario? Explain.

(c) (2 points) What is a worst-case runtime scenario? Explain.

(d) (7 points) Prove a tight bound for the worst-case runtime. Show all your work.

4. Consider the following algorithm, where P and S are arrays of characters (i.e., strings), and answer the questions below. The notation represents logical negation (i.e., flip the proceeding variable value from true to false, or visa versa) Require: PO,m , S,n], for 1