(C++) Given the following pseudo code: Algorithm What (A, n) A <- new 2-dimensio
ID: 673162 • Letter: #
Question
(C++) Given the following pseudo code:
Algorithm What (A, n)
A <- new 2-dimensional array of n x n integers
s <- 0
for i <- 2 to n-2 do
for j <- i-2 to n-1 do
s <- s + A[i ][j ]
end for
end for
Answer the following questions:
2.a What is the Big-O order of the memory required by the algorithm?
2.b What is the Big-O order of the operations required by the algorithm?
2.c How many times is the statement in the innermost loop executed, as a function of n? :
2.d What are the best and worst case scenarios of order of operations of this algorithm?
Problem 3. Write the order (big-O) of an algorithm with the following number of operations, as a function of the problem size n (note: k is constant):
3.a 2n + n^0.5 + 0.5n^1.25 operations :
3.b k^2 log(n) + k(log (n)^2) operations :
3.c log(n) + log (log(n)) operations :
Explanation / Answer
2a) Since we are filling a 2d array. memory req = O(n^2)
b) Operations required = O(n^2)
c) n-1 + n-2 + n-3 ... + 1 = n(n-1)/2
d) Both are same. O(n^2)
3a) O(n^1.25)
b) O(log(n)^2)
c) log(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.