Python time complexity convert O(n^2) code to O(n)-CodePudding

The recursive function dumbo_func, which has been preloaded into the answer box, has O(n^2) performance. Rewrite it (still using recursion) so that its performance becomes O(n). Your function will be tested in a loop calling it 20 times with a list of up to 10,000 elements and will time out if the function is still O(n^2 ).

Note that the function is preceded by code to increase the maximum recursion depth. You will need to include that code when doing your own testing and when submitting your answer. However, under Microsoft Windows you'll probably crash the Python interpreter if you try lists of more than about 2000 elements. On a lab machine or on the quiz server, a list size of 10,000 will be fine, provided you've made the necessary change to the code so it's O(n) rather than O(n2).

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) == 0:
        return 0
    else:
        if (data[0] // 100) % 3 != 0:
            return 1   dumbo_func(data[1:])
        else:
            return dumbo_func(data[1:])

#Test1
#Simple test with short list.
#Original func works fine on this
#Result: 3
data = [677, 90, 785, 875, 7, 90393, 10707]  
print(dumbo_func(data)) 


#Test2
#This test will timeout with a O(n^2) function
#Result: Yay!
ok = True
for i in range(20):
    # Repeat enough times to ensure timeout on O(n^2)
    data = list(range(10_000))
    right_ans = secret_version(data)
    your_ans = dumbo_func(data)
    if your_ans != right_ans:
        print("Sorry, but no banana")
        ok = False
        break
if ok:
    print("Yay!")

I wrote my code as below which pass test1 but doesn't pass test2. Isn't my code O(n)? Please advise where inappropriate.

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) == 0:
        return 0
    else:
        return int((data[0] // 100) % 3 != 0)   dumbo_func(data[1:])

CodePudding user response：

Here's a simple guide on list slicing. Long story short, the recursive function is O(N^2) because slicing the list each time to call the function recursively takes O(N) time per each slice.

Solution: try sending the index of the first element of the subarray you're considering to the recursive function, rather then sending the entire sliced array as an argument.

Hint: def func(data, index_of_first_element) rather than def func(data)

CodePudding user response：

I tried sending the index to the subarray but the time limit exceed for [0]*10000

import sys
sys.setrecursionlimit(100000)

def dumbo_func(data, start_index=0):
    """Takes a list of numbers and does weird stuff with it"""
    if len(data) - start_index == 0:
        return 0
    else:
        if (data[start_index] // 100) % 3 != 0:
            return 1   dumbo_func(data, start_index 1)
        else:
            return dumbo_func(data, start_index 1)

data = [677, 90, 785, 875, 7, 90393, 10707]
print(dumbo_func(data))
data = [0]*10000 
print(dumbo_func(data))