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 ?
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.