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

cs.stackexchange https://cs.stackexchange.com/questions/105579

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top