Question about 12.9 in 1.4.7

#1

My intuitive approach of this problem is to divide the matrix into 4 parts. Each iteration compares x to the max value (bottom right corner element) of the top left section, let’s call it y1, as well as the min value (top left corner element) of the bottom right section, let’s call it y2. If x > y1, then next iteration ignores the top left section. If x < y2, next iteration ignores the bottom right section. This approach will be pretty complex to code, but I’m having a hard time to understand the time complexity of it. Should it be T(n) = 3T(1/4n) + 2 if we treat n as the number of elements, or T(n) = 3T(1/2n) + 2 if we treat n as the square root of the number of the elements, or T(n) = 3*T(n-1) + 2 if n is the log of the square root of element count? What’s the time complexity? Gosh my math is so rusty.

0 Likes
#2

Hey Ray,

Try to read the following two links and you should learn how to calculate this :smile:

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-2-asymptotic-notation-recurrences-substitution-master-method/

1 Like
#3

Thanks a lot Tsung-Hsien. I totally forgot about master theorem. So if i’m right about the size of the problem, the recurrence should be T(n) = 3*T(n/4) + O(1). Then T(n) = Θ(n^log(4,3)), which is better than Θ(n). Am I right or miscalculating something?

0 Likes
#4

In fact, I haven’t calculated this for a long time :stuck_out_tongue: so I have no idea yours is correct or not. If any other one is willing to verify this, please feel free to comment here.

0 Likes