CODEWITHSUNDEEP
arraysalgorithmdata-structuresbinary-searchdivide-and-conquer
Eagle186f
Eagle186f

Reputation: 55

Binary search complexity analysis (Uneven Split)

Design a search algorithm that divides a sorted array into one third and two thirds instead of two halves as in binary search algorithm “BinSrch”. Analyze the time complexity of the algorithm.

I am done with writing the algorithm , need help with the complexity analysis part , could someone please explain what the recurrence relation will look like ?

Upvotes: 1

Views: 1493

Answers (2)

Lorem Ipsum
Lorem Ipsum

Reputation: 4534

@felisimo is totally correct. If you're wondering why the base is 3/2 when splitting on the third, as I was, let me explain.

With binary search, we halve the problem space on each iteration:

For example,

         cut
          |
          V
+----+----+----+----+
| 1  | 2  : 3  | 4  |
+----+----+----+----+
\        /\        /
    1/2       1/2

step 1:
+----+----+
| 3  : 4  |
+----+----+

step 2:
+----+
| 4  |
+----+

For a problem size n, we require x steps to get to a single item:

    <---x times--->
[[n * 1/2] * 1/2] * ...] = 1

n * (1/2)^x = 1
  n * 1/2^x = 1
          n = 2^x
   log_2(n) = x    (by definition of logarithm)

In the example n=4, so the number of steps x is log_2(4) = 2 (since 2 is the power we must raise 2 to get 4).

If we now split by thirds, the problem size reduces to 2/3 its original size on each iteration:

    cut
     |
     V
+----+----+----+----+
| 1  : 2  | 3  | 4  |
+----+----+----+----+
\   /\             /
 1/3       2/3

step 1:
+----+----+----+
| 2  | 3  | 4  |
+----+----+----+

... (waives hands)

As before,

 n * (2/3)^x = 1
     (2/3)^x = (1/n)
[(2/3)^x]^-1 = (1/n)^-1
     (3/2)^x = n
log_{3/2}(n) = x        (by definition of logarithm)

Here we can see where the 3/2 comes from. Since 2/3 is left over after each iteration, the reciprocal shows up as the base just because that's how the math works out.1 For our example, the math shows us that it would take

log_{3/2}(4)= log(4)/log(3/2) ~ 3.419

cuts to get down to one item. That's kinda funky, but if we take the floor, or just 3, it makes a little more sense. We can see that it takes (marginally) more effort to third the problem than to halve it. However, if you were to plot these two functions, log_2(n) and log_{3/2}(n), you'd see they're almost the same.

plots of log_2(n) and log_{3/2}(n)

The real power comes from the log.2

1 At least, I can't think of an intuitive explanation for why the base is 3/2.

2 Pun intended :)

Upvotes: 1

felisimo
felisimo

Reputation: 364

If this were a regular binary search, the worst time complexity would be achieved if your desired element would be the last one remaining in the array after cutting half of the array each iteration. The answer to the question "how many times can I divide this array in half until it has 1 element left" is log(n) with a base of 2 - henceforth log2(n). That's why the time complexity for the regular bin search is log2(n).

The same logic can be applied for your case. You again need to prolong the search as much as possible, and that would happen if each iteration you go with the bigger part of the array - the 2/3rd part - because that would cause it to decrease in size slowest. So, how many times can you cut the remainder of the array to two-thirds until it has 1 element remaining? Again log(n) but this time with a base of 1.5 - log1.5(n).

Lastly, remember from logarithm rules that for known bases a,b: loga(n) = logb(n) * loga(b), so in our case log1.5(n) = log2(n) * log1.5(2) That 3rd part is a constant, so our efficiency is the same as the regular binary search efficiency, only multiplied by some constant - which keeps it a time complexity of log(n). Long story short, the base doesn't matter.

Upvotes: 3

Related Questions