Give a big-Oh characterization, in terms of n, of the running time of the Ex1-EX

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

Explanation / 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)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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