How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

Question

How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

If I have a recursive function like this for example (This is just an example, its not a real thing, it just demonstrates my question):

someFunction(n){
  base case:
    return 0
  if (some case)
    return someFunction(3n/4)
  else if (some other cases)
    return someFunction(n/4)
}

As we can see, the recursion calls itself in different cases and in different cases, the n is fractioned by different value, how can I write down the recursive formula for finding out the run time?

Is the formula something like:

T(n) = T(3n/4)?
T(n) = T(n/4)?
T(n) = T(3n/4) + T(n/4)?
T(n) = (Probability of first case)*T(3n/4) + (Probability of first case)*T(n/4)?

What if I have no idea what is my probability for each case?

Answer 1

If you want to find the worst-case asymptotic running time, then you can't use probabilities; you have to assume that at each branch, it takes the slower path. Thus you get a recurrence relation

$$T(n) = \max(T(3n/4), T(n/4)) + O(1).$$

If you want to find the expected running time, then you can use probabilities:

$$T(n) = p_0(n) T(3n/4) + p_1(n) T(n/4) + O(1)$$

where $p_0(n)$ is the probability of taking the "then" branch and $p_1(n)$ is the probability of taking the "else" branch. If you don't know the probabilities, this kind of analysis won't be useful and you presumably won't be able to calculate the expected running time. There are some important caveats here as well; the random choice must depend only on internal random choices of the algorithm, not on $n$, or else funny things can happen.

Solving the recurrence relations above is a separate matter. Often it suffices to apply the master theorem.

Normally, in theoretical computer science, if we are talking about asymptotic running time, the default assumption is that you are talking about worst-case running time. If you want to focus on something else (e.g., expected running time), it's important to state that explicitly, otherwise you might cause confusion among readers.

Since you seem to lack some basic understanding of running time analysis, I suggest studying big-O notation, running time analysis, and recurrence relations. This is a slightly tricky example, and it's not the simplest one to start with to start learning the subject. We do have some resources on that subject here; see, e.g., How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Sorting functions by asymptotic growth, Is there a system behind the magic of algorithm analysis?, Solving or approximating recurrence relations for sequences of numbers, and a good algorithms textbook.

Answer 2

Well, it is called maths. You’d have to figure out when and how often “some case” and “other case” happens, if there is a system that you can detect, and so on. For an upper bound, you may assume that you always take the branch that takes longer; that upper bound might be much too high.

Once you encounter problems that don’t fit into well-known patterns, you just have to handle them individually.