Find the worst-case time complexity of the algorithm given below (Follow all ins

Question

Find the worst-case time complexity of the algorithm given below (Follow all instructions!):

2. Find the worst-case time complexity of the DeeperMystery algorithm on the next page, in the case where n is a power of 2 (n = 2k for some integer k). Express your final answer in terms of n. Show your work Hint: all exponential series are dominated by their largest term. More formally, al era"), for any x > 0 and a > 1. Input: mat: n x n matrix of integers Input: n: size of mat (power of 2) 1 Algorithm: DeeperMystery 2 whilen>1do 3Let ul, ur, ll, and lr be the upper-left, upper-right, lower-left, and lower-right quadrants of mat, respectively 4Calculate the sum of the elements in ul, ur, ll, and lr 5 if ul had the max sum mat-ul then 6 7else if ur had the max sum then 8 mat - ur 9else if ll had the max sum then 10 11else 12 13 end 14n n/2 15 end mat, 11 matlr 16 return mat1, 1

Explanation / Answer

Let's assume in the 1st pass, it has to calculate all 4 quadrants of the matrix to find the highest matrix.

Let the time for calculating max for all 4 matrices be n.

Then, going on to the 2nd pass, it determines one of the matrix as the max matrix. Note that the size of the matrix is now n/4. So, each matrix will be of size n/16. So in the worst case, it has to traverse all the 4 submatrices of this. So, in this case it will have to traverse n/4 elements.

Similarly, for rest of the submatrices, it would be n/16, n/64, .......

Worstcase time for calculating = n + n/4 + n/16 + n/64 + ......

= n(1 + 1/4 + 1/16 + 1/64 + .....)

= n(40 + 4-1 + 4-2 + 4-3 + ....)

= O(n) { based on the assumption given, all exponential series are dominated by their largest sum }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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