Big O of a recursive function

I'm learning Big O notation but am stuck when it comes to recursion. This is a fairly new topic to me, I was taught to solve this either using substitution or the master method. I don't know how I would apply this to pseudo code though.

    def isThis(n): 
        print(n) 
        if (n == 1):
            return True
        if (n == 0): 
            return False
        if (( n % 3) == 0):
            return (isThis(n/3))
        else:
            return False

My understanding is that this algorithm will run O(n) if we use T(n) = aT(n/b) + f(n), where a = 1, b = 3 and d = 1

'a' is number of recursive calls

'b' is factor of the subproblem

'd' is exponent of the running time outside of the recursive call.

But I have no idea if I'm doing this correct or tackling it in the completely wrong way.

Any help or suggestions would be appreciated.

Your code runs in O(log(n)) arithmetic operations of course, since in the worst case it performs as much operations as there are ternary digits. If you want to apply the master theorem, your case is case 2 from wikipedia, since f(n) = O(1).

Note that this asymptotic description is in arithmetic operations. This code does not run in O(log(n)) time since every arithmetic operation does not run in O(1) time.

The Master Theorem formula using Landau notation is:

T(n) = aT(n/b) + O(n^d)

Where :

• n is the size of the input,
• T(n) is the time complexity of the algorithm for a problem of size n.
• a is the number of sub-problems generated by the algorithm during each recursion.
• n/b is the size of the sub-problems. This assumes that the algorithm divides the initial problem into sub-problems of size n/b.
• O(n^d) is, expressed as a Big O notation, the cost of merging the sub-problem solutions and all other non-recursive operations performed.

In the algorithm you've given, the function isThis(n) performs
a recursion based on dividing n by 3 until n
reaches 1 or some other stopping condition. So, we can consider n to be the size of our input, and:

• a = 1, as the recursion generates only one sub-problem at each
  iteration (There will only be a maximum of one call to isThis inside inThis).

• b = 3, because n is divided by 3 at each recursion (each call of isThis)

To determine O(n^d), we see that the cost of the verification operation (condition and return) is constant, regardless of the size of the the input n.
So O(n^d) = O(1), thus d = 0.

Now with a, b and d, we can check which case of the Master Theorem match our case :

• Case 1 : if d < log_b(a) then T(n) = O(n^log_b(a))
• Case 2 : if d = log_b(a) then T(n) = O(n^d log_b(n))
• Case 3 : if d > log_b(a) then T(n) = O(n^d)

In our case, we have log_b(a) = log_3(1) = 0

And we also have d = 0.

So we are in the second case, and the complexity of your function is :

O(n^d log_b(n)) = O(n^0 log_3(n)) = O(log_3(n)), simplified as O(log(n)).