Strategy for figuring out input size of recurrence equation?

Question

Something I'm struggling with is figuring out a precise way of knowing how our size n should be defined. To demonstrate what I mean by that; take for example binary search. The input size n of T(n) is defined to be high - low + 1. I don't really understand how we can

1. Figure that out from just the algorithm without taking an "educated guess"
2. confirm that we are not wasting our time proving the recurrence equation with a falsely derived input size

I would really appreciate some advise, thanks in advance.

Answer 1

Indeed the input size is usually not arbitrary. It is necessary to correctly determine what that is.

So how do we do it?

First of all you have to understand the algorithm - what it does and why do you even use it. Usually you can brute force any problem quite easily, but you still decide to use something better. Why? Answering that question should make everything clear.

Let's take a look at your binary search example. You want to find a specific value by calling a monotonic function that will tell you if your choice is too low or too high. For example, you may want to find a largest value less than a specific number in an array.

What is a brute force approach? Well, you can ask for every value possible. What affects the complexity? The number of values you can choose. That's your input size. To decrease the complexity you may want to use the binary search, which let's you do much less queries. The input size remains the same.

Let's have a look at some other algorithms:

• Euclidean algorithm for GCD - brute force? Search for every number less or equal to the minimum of your input. What affects the complexity? The number of values you want to check, that is the numbers for which you want to find the GCD.
• BFS/DFS (graph traversal) - you want to visit each node once. For each node you have to additionally check every edge. In total: the input size is the number of nodes and edges.
• KMP/Karp-Rabin/any other pattern finding algorithm - you want to find occurences of pattern in a text, the input size will obviously be a text size, but also a pattern size.

Once you understand the problem the algorithm solves, think of a brute force approach. Determine what affects the speed, what can be improved. That is most likely your input size. In a more complex cases, the input size is stated in an algorithm's description.