Time complexity of a recursive function depends on the number of times the
function is calling himself multiply this by the each time how many time
complexity is taken on each call it can be O(1), O(log n), O(n) or more.
Let's say our function is calling n-1 times and each it is doing some
comparisons and call it self again. So function itself has a time complexity of
O(1).
So the total time complexity will be (n-1)*1 which is o(N).