Search Algo Complexity: Number of times you can take 3/4th of a number until it is less than or equal to 1

Question

I'm working on a variant of binary search that narrows the search space down to 3/4th its original size every iteration and am wondering how you'd go about figuring out its runtime.

My intuition says it's log base (4/3) of N (where N = the size of the array you're searching) but I'm struggling to prove this.

Answer 1

Yes, you are correct.

Here is a proof:

Let's take it from the reversed direction. We arrived at a value 0 < n ≤ 1. Before the last iteration, n must have been such that:

      1 < n ≤ 4/3,

Before the one-but-last iteration:

      4/3 < n ≤ (4/3)²

and so on... So backtracking k iterations we get:

      (4/3)^k−1 < n ≤ (4/3)^k

If we take the (4/3)-base logarithm of all parts in this inequality:

      k − 1 < log_4/3n ≤ k

So if you round that logarithm up, you get k, which represented the number of iterations.