Let's say I have a code like this,

def func1(arr):
    arr = sorted(arr)
    for i in range(len(arr)):
         # something in here
    return some_val

What would be time complexity in this case? Is it O(n) because of the for loop? I have a sorted function of O(n*log(n)) before the loop is called on the sorted input list. In this case what would be total time complexity of the whole problem?

CodePudding user response：

Here the time complexity will be O(nlog(n)). The loop runs in linear time, O(n). The O(nlog(n)) sorting operation is the more expensive operation. Since the sorting and the loop are done sequentially one after the other, the most expensive operation determines the Big-O of the function. This is assuming # something in here is a O(1) operation.

CodePudding user response：

def func1(arr):
    arr = sorted(arr) // Here O(n*log(n))
    for i in range(len(arr)): // Your loop O(n)
         # something in here
    return some_val

Based on your code the total time complexity O(nlog(n)) O(n) since the growth of the log-linear function is higher than linear function then we can omit O(n). The final complexity will be O(nlog(n))