Given the following algorithms below give a bigOh characteri

Given the following algorithms below, give a big-Oh characterization of the running time in terms of the size of the input, n. Provide justification (description, equations, and/or diagrams) for your answer. public static boolean two_sum(int[] arr) {for (int i=0;

Solution

for(int i=0; i<arr.length;++i ) ===========> Runs for n+1 times , as array length is n and 1 for failure case
     for(int j=0; j<arr.length;++j )  ===========> Runs for n(n+1)/2 times , runs n times because of outer for loop and n , n-1, n-2 , n-3 .. . .1 , so total it runs n(n-1)/2
   if(i!=j . && arr[i] + arri[j] = 2) ===========> Runs for nearly n(n-1)/2times , runs n times because of outer for loop and n , n-1, n-2 , n-3 .. . .1 , so total it runs n(n-1)/2
   return true --------> Once


So overall time complexity is

T(n) = n + n*(n-1)/2 + n*(n+1)/2 + 1
=> T(n) = O(n²)




2) for(int i=0; i<42 ++i ) ---> Runs for max 43 times irrespective of n [once for failure scenarion when i becomes 42]
   n = n +i =======Runs for max 42 times irrespective of n


So above code doesnot depend on n

So T(n) = 42 , which is a constant

=> T(n) = O(1)



Thanks, let me know if there is anything.