The merge method receives $2$ strings sorted in ascending order as input and "merges" them into

a single string $-$ also sorted in ascending order.

i$.$e$.$ Given: "acf" and "bde", merge $("$acf$",$ "bde"$)$ returns "abcdef",

Implement method merge using recursion:

a$.$ What is the base case$($s$)?$ Pseudocode or a clear English explanation will work.

b$.$ What does "size of input", $n,$ refer to in this method?

c$.$ What is the Big$-$O for this method? Explain your reasoning.

d$.$ Can this method be considered Big$-$Omega of the function in c$?$ Explain your reasoning.

e$.$ Can this method be considered Big$-$Theta of the function in c$?$ Explain your reasoning.

f$.$ Recursive Implementation:

String merge$($String str$1,$ String str$2)\{$

$\}$

Provide a generic interface for the following interface:

public interface IStack $\{$

char pop$()$;

void push $($char c$)$;

char top$()$;

int length$()$;

boolean isEmpty$()$;

$\}$