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

return;

else $\{$

int$[]$ leftHalf $=$ new

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

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

$i++$

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

$\}$

divideAndConquer$($leftHalf$)$;

int$[]$ rightHalf $=$ new

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

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

$i++$

rightHalf $[i]=$

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

$\}$

divideAndConquer$($right$)$;

$\}$

$\}$