Find the running time functions and classify the algorithms using Big-O asymptot

ID: 669131 • Letter: F

Question

Find the running time functions and classify the algorithms using Big-O asymptotic notation

Algorithm Ex1(A):
Input: An array A storing n 1 integers.
Output: The sum of the elements at even cells in A.

s A[0]
for i2 to n1 byincrementsof2do

s s + A[i] return s

Algorithm Ex2(A):
Input: An array A storing n 1 integers. Output: The sum of the prefix sums in A.

s0
fori 0to n1 do

s s + A[0]
for j 1 to n do

s s + A[j] return s

Algorithm Ex2(A):
Input: An array A storing n 1 integers. Output: The sum of the prefix sums in A.

s0
fori 0to n1 do

s s + A[0]
for j 1 to i do

s s + A[j] return s

1) n/2

as we have n numbers in one loop which is incremented by 2 .So,it will be executed n/2 times only.

2) n^2, as we have two loops(recursive looping) in this case which are executed for n times.

3) n^2

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.