CSCI $132$ Lab $9$: Algorithm Analysis and Big$-$O Running Time

Instructions: For each of the four algorithms below, you will need to find the running time of the algorithm and state the total running time in Big$-$O notation. For each operation in the algorithm, you will find the running time$/$time complexity of that operation $($just like we did in class$).$ You can print this out and do it by hand or do it in a word$/$pdf editor. You will not be submitting any code for this lab. This lab is due Thursday October $\backslash (31^\{\backslash$text $\{$st $\}\}\backslash )$ at $11$:$59$ PM$.$

Algorithm $1$: Given an even$-$length array, this algorithm splits the input array into two equalsized sub arrays: split$\_$array$1$ and split$\_$array$2.$

Example Execution:

Input: $[1,2,3,4,5,6,7,8]$

Output array $\backslash$#$1$: $[1,2,3,4]$

Output array $\backslash$#$2$: $[5,6,7,8]$

$```$

public static void split$\_$array$($int$[]$ input$\_$array$)\{$

int$[]$ split$\_$array$1=$ new int$[$input$\_$array.length $/2]$;

int$[]$ split$\_$array$2=$ new int$[$input$\_$array.length $/2]$;

for$($int i $=0$; i $$ input$\_$array.length$/2$;i$++)\{$

split$\_$array$1[$i$]=$ input$\_$array$[$i$]$;

$\}$

int counter $=0$;

for$($int j $=$ input$\_$array.length$/2$; j $$ input$\_$array.length;j$++)\{$

split$\_$array$2[$counter$]=$ input$\_$array$[$j$]$;

counter$++$;

$\}$

System.out.println$("$Output array #$1$: $"+$ Arrays.toString$($split$\_$array$1))$;

System.out.println$("$Output array #$2$: $"+$ Arrays.toString$($split$\_$array$2))$;

$\}$

$```$