Find the running time functions for the algorithms below and

Find the running time functions for the algorithms below and write their classification using Big-O asymptotic notation. The running time function should provide a formula on the number of operations performed on the variable s. Algorithm Exl(A): Input: An array A storing n greaterthanorequalto 1 integers. Output: The sum of the elements in A. s leftarrow A[0] for i leftarrow 1 to n - 1 do s leftarrow s + A[i] return s Algorithm Ex2(A): Input: An array A storing n greaterthanorequalto 1 integers. Output: The sum of the elements at even positions in A. s leftarrow A[0] for i leftarrow 2 to n- 1 by increments of 2 do s leftarrow s + A[i] return s Algorithm E times 3(A): Input: An array A storing n greaterthanorequalto1 integers. Output: The sum of the partial sums in A. s leftarrow 0 for i leftarrow 0 to n - 1 do s leftarrow s + A[0] for j leftarrow 1 to i do s leftarrow s + A[j] return s Algorithm Ex4(A): Input: An array A storing n greaterthanorequalto

Solution

1. Ex1(A) :

In this algorith ,for loop is repeated n-1 times .other statments are executed constant time in c ;

In Big O notation time complexity =O(n-1) +C ==== O(n)

2.Ex2(A) :

In this algorith ,for loop is repeated (n-2)/2 times to add even numbers .other statments are executed constant time in c ;

In Big O notation time complexity =O((n-2)/2) +C ==== O(n/2)

3.Ex3(A) :

In this algorith ,external for loop is repeated (n-1) times and inner for loop is repeated max of n-1 times .other statments are executed constant time in c ;

In Big O notation time complexity =(n-1)*(n-1) +C ==== O(n²)

4.Ex4(A) :

In this algorith , loop is repeated (n-1) times repeated .other statments are executed constant time in c ;

In Big O notation time complexity =O(n-1) +C ==== O(n)