CODEWITHSUNDEEP
algorithm
giulio
giulio

Reputation: 659

2D Peak finding in linear time

I am reading this O(n) solution of the 2D peak finding problem. The author says that an important detail is to

split by the maximum direction. For square arrays this means that split directions will be alternating.

Why is this necessary?

Upvotes: 1

Views: 1229

Answers (2)

Mark Shevchenko
Mark Shevchenko

Reputation: 8197

This is not a necessary. The alternating direction gives O(N) for any arrays.

Let's count the number of comparisons for an array M × N.

First iteration gives 3×M, second gives 3×N/2, third gives 3×M/4, fourth gives 3×N/8, i.e.:

3 * (M + M/4 + M/16 + ...) + 3 * (N/2 + N/8 + N/32 + ...)

We got two geometric series. Cause both of these series has common ratio 1/4, we can calculate the upper limit:

3 * (4 * M/3 + 2 * N/3)

Cause O(const × N) = O(N) and O(M + N) = O(N), we have O(N) algorithm.

If we always choose the vertical direction, then performance of algorithm is O(logM × N). If M much more N, then this algorithm will be faster. F.e. if M = 1025 and N = 3, then count of comparisons in the first algorithm is comparable to 1000, and in the second algorithm is comparable to 30.

Splitting an array by the maximum direction, we got the faster algorithm for specific values of M and N. Is this algorithm O(N)? Yes, cause even comparing both vertical and horizontal sections at each step we have 3 × (M + M/2 + M/4 + ...) + 3 × (N + N/2 + N/4 + ...) = 3 * (2 × M + 2 × N) comparisons, i.e. O(M + N) = O(N). But we always choose only one direction at each step.

Upvotes: 4

tmyklebu
tmyklebu

Reputation: 14205

Splitting the longer side ensures that the length of the split is at most sqrt(area). He could have also gone through the proof noticing that he's halving area with each call and he looks at most 3 sqrt(area) cells to do so.

Upvotes: 0

Related Questions