Question

Give a big-Oh characterization, in terms of n, of the running time of the Ex1-EX5 functions as shown in following Code Fragment ..

Algorithm
Ex1 ( A):
Input:
An array A storing n?1 integers.

Output:
The sum of the elements in A.
s? A[0]
for i?1 to n?1 do
s?s+ A[i]
return s

Algorithm
Ex2( A):
Input: An array A storing n?1 integers.
Output:
The sum of the elements at even cells in A.
s? A[0]
for i ?2 to n?1 by increments of 2 do
s?s+ A[i]
return s

Algorithm
Ex3 ( A):
Input: An array A storing n?1 integers.
Output:
The sum of the pre?x sums in A.
s?0
for i?0 to n?1 do
s?s+ A[0]
for j?1 to i do
s?s+ A[ j]
return s

Algorithm
Ex4( A):
Input:An array A storing n?1 integers.
Output:
The sum of the pre?x sums in A.
s? A[0]t ?s
for i?1 to n?1 do
s?s+ A[i]
t ?t +s
return t

Algorithm
Ex5 ( A, B):
Input:Arrays A and B each storing n?1 integers.
Output:
The number of elements in B equal to the sum of pre?x sums in A.
c?0
for i?0 to n?1 do
s ?0
for j?0 to n?1 do
s?s+ A[0]
for k ?1 to j do
s?s+ A[k ]
if B[i] =s then c?c+1
return c

Answer 1

Answer:

Hello there, Please follow the step by step explanations for answer.

Explanation:

Hello there, Please follow the step by step explanations for answer.

Ex1 ( A):

it depends on n

=> O(n)

2.)

O(n/2) which is equal to O(n)

3.)O(n^2)

4.)O(2n) ==> O(n)

5.)O(n^3)

Also, see file attachment on this question for more clarity. Thanks and all the best.