Find running time functions for the algorithms below and write their classification using Big-O asymptotic notation...

 

Transcribed Image Text:

Find running time functions for the algorithms below and write their classification using Big-O asymptotic notation in terms of n. A running time function should provide a formula on the number of arithmetic operations and assignments performed on the variables s, t, or c (the return value). Note that array indices start from 0. 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] end for return s Algorithm Ex2 (A) : Input: An array A storing n ≥1 integers. Output: The sum of the elements at even positions in A. s ← A[0] for i 2 to n-1 by increments of 2 do s + s + A[i] end for return s A Find running time functions for the algorithms below and write their classification using Big-O asymptotic notation in terms of n. A running time function should provide a formula on the number of arithmetic operations and assignments performed on the variables s, t, or c (the return value). Note that array indices start from 0. 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] end for return s Algorithm Ex2 (A) : Input: An array A storing n ≥1 integers. Output: The sum of the elements at even positions in A. s ← A[0] for i 2 to n-1 by increments of 2 do s + s + A[i] end for return s A

Answer rating: 100% (QA)

Step 1 Big O notation often referred to as time complexity analysis is a mathematical notation used in computer science to describe the upper bound on ... View the full answer