Suppose you are given a matrix A n of size n × n, where elements are sorted alon

Question

Suppose you are given a matrix An of size n × n, where elements are sorted along every column and every row. For example:

A4=

Suppose we want to check if x is an element of matrix An or not. You can do this with a divide and conquer method. One algorithm is to use a binary search routine to check each row for the input integer x. Another algorithm is that if matrix An is represented in block-view:

An =

where all matrices A1 , A2 , A3 , A4 are of the size n/2 × n/2 , then one can compare element x with A4 [1, 1] and consider only three options:

1. x = A4 [1, 1] then the algorithm can output ”yes”.

2. x < A4 [1, 1] then he knows that i, j < n/2 : x < A4 [i, j], thus he knows for sure that x is not in A4 , and only need to recursively apply his algorithm to check if x A1 , x A2 or x A3 .

3. x > A4 [1, 1] then he knows that i, j < n/2 : x > A1 [i, j], thus he knows for sure that x / A1 , and only need to recursively apply his algorithm to check if x A2 , x A3 or x A4 .

Whose algorithm is faster on the worst case input? Prove your statement.

Explanation / Answer

In the first case, finding x in the first attempt(A[0,0]) is the best case. In the second case if x=A[1,1] is the best case. In the second case it then searches either left tree (x<A[1,1]) or the right tree(x>A[1,1]).

Worst case in first case is to find the last element as x i.e., A[7,7]. Worst case in second case is to find the element in one of the last division A4 last element.

Faster one is second when the first element is A[1,1] and is first one fi A[0,0] is x

Worst case input is the first one giving entire matrix. Second case is best input method. It is already divided into subtrees, selection among smaller sub trees reduces space complexity and increases performance.

o(1) is the best case time complexity in first, second cases. O(log(n/4)) is the time complexity in second case as it it searches in one of 4 sub trees. O(n) is the time complexity of first case(binary search)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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