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];
}
}
}

Solutions

Expert Solution

venereology answered 10 months ago

Next > < Previous

Related Solutions

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...

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

In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your...

In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation. 1.Show that if a binary tree has a vertex with a single child, then this can not be an optimal Huffman tree. 2. Question...

What is the auxiliary space and space complexity for a dynamic programming algorithm with time complexity...

What is the auxiliary space and space complexity for a dynamic programming algorithm with time complexity of O(n^2)? Justify.

Subjects