I was given the following question:

Given the following algorithm:

Function f1(a, b)
// a: int
// b: int

if b == 0
    return b
else
    return a   f1(a, b-1)

Determine the best and worst case complexity for this algorithm

I answered with O(n) and Ω(1)

• As when b -> ∞ and a ∈ Z, you decrease b by 1 each time (T(n) = 1 T(n-1)) which implies a runtime of O(n)
• But when when a -> ∞ and b = 0, you always return on the base case immediately, hence Ω(1)

But the answer was:

O(n) and Ω(n)

Why is this so?

Is n assumed to be b, and Ω(1) is simply Ω(n) because n = 0?

CodePudding user response：

Case 1: when b -> ∞ and a ∈ Z, complexitites will be O(n) and Ω(1)
Case 2: for a -> ∞ and b = 0, complexities will be O(1) and Ω(n)

So considering both cases, the best case complexity is O(n) and the worst case is Ω(n)

CodePudding user response：

There function will have b recursive calls regardless of value of a. So, n is assumed to be b. In both best case and worst case scenarios the time complexity is same.

Hence, the best case time complexity is O(n) and the worst case time complexity is Ω(n)