Give the asymptotic (“big-Oh”) running time complexity of the following algorithm, show all the work you...

Give the asymptotic (“big-Oh”) running time complexity of the following
algorithm, show all the work you have done.

Algorithm: ArrayMangle(A[ ], int n)
Input: an array A, an integer n
x = 0;
for (i=0; i<=n-1; i++) {
for (j=i; j<=n-1; j++) {
x = x + A[j];
}
for (k=0; k<= n-1; k++) {
for (j=0; j< =n-1; j++) {
x = x + A[j]*A[k];
}
}
}

Expert Solution

venereology answered 1 year ago

For each of the following six program fragments give an analysis of the running time (Big-Oh...

For each of the following six program fragments give an analysis of the running time (Big-Oh will do). (25,very 5 mark) (a)sum = 0; for( i=0; i<n; i++ ) for( j=0; j<n; j++ ) sum++; (b) sum = 0; for( i=0; i<n; i++ ) for( j=0; j<n*n; j++ ) sum++; (c) sum = 0; for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) sum++; (d) sum =0; for( i=1; i<n; i++ ) for( j=1; j<i*i; j++ ) if( j%1...

Question 15: Use the Master theorem to find the asymptotic complexity of the running time function...

Question 15: Use the Master theorem to find the asymptotic complexity of the running time function T(n) of the program in problem 14. --- Problem 14 --- def prob14(L): if len(L) <= 1: return 0 output = 0 for x in L: for y in L: output += x*y for x in L: output += x left = L[ 0 : len(L)//2 ] right = L[ len(L)//2 : len(L) ] return output + prob15(left) + prob15(right) ***Big-O, Omega, Theta complexity...

Find the Asymptotic time complexity for each of the functions in the following: #Q2 # to...

Find the Asymptotic time complexity for each of the functions in the following: #Q2 # to denote ayymptotic time complexity use the following notation # O(l) O(m) O(a) O(b) # e.g. traversing through l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is O(l) #1 def merge(): l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] m = [15, 16, 17, 18] lm = [] for l_i in l: lm.append(l_i) for m_i in m:...

Purpose This project is meant to give you experience with sorting, binary searching, and Big-Oh complexity....

Purpose This project is meant to give you experience with sorting, binary searching, and Big-Oh complexity. Objective "Write in Java please" Your goal is to take a book, as a large text file, and build a digital “concordance”. A concordance is like an index for a book in that it contains entries for words in the book, but it also includes passages from the book containing that word. For example, a query for the word Dormouse in Alice in Wonderland...

Calculate the time complexity of each algorithm for best, worst and average cases. Give all steps...

Calculate the time complexity of each algorithm for best, worst and average cases. Give all steps of your calculation and results in Big-O notation. algorithm : Selection Sort Bubble Sort Insertion Sort

Implement 2-D peak finder and explain the asymptotic complexity of the algorithm For Design and Analysis...

Implement 2-D peak finder and explain the asymptotic complexity of the algorithm For Design and Analysis of the Algorithme lecture

Q1) (1 point) Design an efficient algorithm (in terms of asymptotic complexity in the worst case)...

Q1) (1 point) Design an efficient algorithm (in terms of asymptotic complexity in the worst case) to determine if two students in a class of n students have the same height. What is the complexity of your algorithm? a.Provide the pseudo-code of that algorithm. b.Implement the algorithm in a language of your choice and provide a sample run with meaningful input.

Question 2: Calculate the time complexity function T(n) and express it in terms of big-Oh for...

Question 2: Calculate the time complexity function T(n) and express it in terms of big-Oh for the following code: Part a (hint: make use of sum of geometric progression): for (int i=1; i <= n ; i = i*2) { for ( j = 1 ; j <= i ; j ++) { cout<<”*”; } } Part b (hint: make use of sum of square of a number sequence): for (int i=1; i <= n ; i...

Calculate the Big-O time complexity. Show work 1. n^2 + 3n + 2 2. (n^2 +...

Calculate the Big-O time complexity. Show work 1. n^2 + 3n + 2 2. (n^2 + n)(n ^2 + π/2 ) 3. 1 + 2 + 3 + · · · + n − 1 + n

Give pseudocode to implement a phase of Boruvka’s algorithm. Argue that ˙ the running time of...

Give pseudocode to implement a phase of Boruvka’s algorithm. Argue that ˙ the running time of your implementation is O(m)

Question