CODEWITHSUNDEEP
time-complexityspace-complexity
beginner
beginner

Reputation: 1

Time and Space Complexity of a Recursive Algorithm

Convert n to its English words representation, where 0 <= n < 1,000,000,000

Python Solution:

class Solution:
    def helper(self, n):
        ones = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']
        teens = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
        tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']

        res = ''
        if n < 10:
            res = ones[n]
        elif n < 20:
            res = teens[n - 10]
        elif n < 100:
            res = tens[n // 10] + ' ' + self.helper(n % 10)
        elif n < 1000:
            res = self.helper(n // 100) + ' Hundred ' + self.helper(n % 100)
        elif n < 1000000:
            res = self.helper(n // 1000) + ' Thousand ' + self.helper(n % 1000)
        elif n < 1000000000:
            res = self.helper(n // 1000000) + ' Million ' + self.helper(n % 1000000)
        return res.strip()


    def convert_to_word(self, n):
        if n == 0:
            return 'Zero'
        return self.helper(n)

I've been trying to calculate the time and space complexity of this solution. I've seen different answers. Some say that the time complexity is O(1) because the helper function is called a fixed number of times (even if n is a large number). Others say it's O(log(n)).

The space complexity seems to be O(1)?

I am so confused. Please help me clarify. Thank you.

Upvotes: 0

Views: 122

Answers (1)

Mo B.
Mo B.

Reputation: 5805

On all inputs n that are larger than 1000000000, the function returns immediately with an empty string, without any computations or recursive calls. So of course the time complexity is O(1), likewise the space complexity (since what happens for smaller n is completely irrelevant).

The case would be different and more interesting if you removed the line

elif n < 1000000000

so that for large n you would get a (virtually) unbounded resulting string with an unbounded number of Million-substrings (ignoring the fact that integers have a maximum size on a real computer, and ignoring the fact that you would get nonsensical number words). In this case you would get the time complexity O(log(n)^2) (since you're concatenating O(log n) strings of length O(log n)) and space complexity O(log n) (because of the call stack for the recursive calls). The time complexity could easily be reduced to O(log n) by handling the string concatenations more efficiently.

Some additional explanation

It seems from the comments that it's not obvious why the time complexity is O(1). If we say that the time complexity T(n) is in O(1), that means that there exists a constant c and a constant k such that for all n > k, T(n) <= c.

In this example, choosing c = 9 and k = 0 does the trick, or alternatively choosing c = 1 and k = 1000000000, hence the time complexity is O(1). It should now also be clear that the following function is also O(1) (albeit with a very large hidden constant factor):

void f(int n) {
   if (n < 1000000000) {
      for(int i = 0; i < n; i++) { 
         for(int k = 0; k < n; k++)
            print(i); 
      }
   }
   else print("");
}

Upvotes: 1

Related Questions