So I'm preparing for the Algorithms exam and I don't know how to solve this recurrence T(n) = T(6n/5) + 1 since b = 5/6 < 1 and Master theorem cannot be applied.
I hope that someone can give me a hint on how to solve this. :)
Given just that recurrence relation (and no additional information like T(x) = 1 when x > 100), an algorithm with time complexity as described by the relation will never terminate, as the amount of work increases at each call.
T(n) = T(6n/5) + 1
= T(36n/25) + 2
= T(216n/125) + 3
= ...
You can see that the amount of work increases each call, and that it's not going to have a limit as to how much it increases by. As a result, there is no bound on the time complexity of the function.
We can even (informally) argue that such an algorithm cannot exist - increasing the size of the input by 1.2 times each call requires at least 0.2n work, which is clearly O(n) - but the actual cost at each step is claimed to be 1, O(1), so it's impossible for an algorithm described by
this exact recurrence to exist (but fine for algorithms with recurrence eg. T(n) = T(6n/5) + n).