What is the run-time complexity in terms of n and m?

user_11433965 0
Viewed 538

This was a coding interview question. What is the run-time complexity of the following algorithm, in terms of n and m?

    def print_all_codes(n, m):
    
        def print_01_codes(current, num_digits):
    
            if num_digits == 0:
    
                print(current)
    
            else:
    
                print_01_codes('0' + current, num_digits - 1)
    
                print_01_codes('1' + current, num_digits - 1)
    
        upper_bound = 0
    
        while True:
    
            for i in range(upper_bound):
    
                print_01_codes('', n)
    
            if upper_bound > m:
    
                break
    
            upper_bound += 1
time-complexity python
1 Answers
 while True:

        for i in range(upper_bound):

            print_01_codes('', n)

        if upper_bound > m:

            break

        upper_bound += 1

This loop is same as this one:

for i in range(m):
    for j in range(i):
       #Function

This loop time complexity is like this: 1 + 2 + 3 + 4 + ... + m-1 => (m-1)*(m) / 2 => O(m^2) about your #Function:


        if num_digits == 0:

            print(current)

        else:

            print_01_codes('0' + current, num_digits - 1)

            print_01_codes('1' + current, num_digits - 1)

This is a recursive function and this is like a full binary tree. So it's O(2^n). Your code Time-complexity is O(m^2 * 2^n).

user_122442030
Related