What is the worst$-$case Big$-$O runtime for the following method? Assume that $n$ is the

length of the array.

public static void

divideAndConquer$($int$[]$ input$)\{$

if $($input$.$length $0)$

$3.,$ return;

else $\{$

int $[]$ leftHalf $=$ new

int$[$input$.$length$/2]$;

for $($int $i=0$;$i$ left Half.length;

$i++$

leftHalf$[$i$]=$ input$[$i$]$;

$\}$

divideAndConquer$($leftHalf$)$;

int$[]$ rightHalf $=$ new

int$[$input$.$length $-$ leftHalf.length$]$;

for $($int $i=0$;$i$ rightHalf.length;

$i++$

rightHalf$[$i$]=$

input$[$leftHalf$.$length $+i$;

$\}$

divideAndConquer$($right$)$;

$\}$

$\}$ T$($n$)=$ O$($log$-$n$),$ T$($n$)=$ O$($n$^2),$ T$($n$)=$ O$($n$.$ log$-$n$),$ T$($n$)=$ O$($n$),$ T$($n$)=$ O$(2^$n$)$