Time complexity of an algorithm in python O(n log n)

This is similar to merge sort. Here you take O(n) time to slice the array as seen here and then you do operations on both halves of the list. Time complexity of merge sort is O(n log(n)).

If you want derivation of merge sort you can take a look at this

This algorithm returns once for each element in the list O(n) It then also implements a bisection search O(log n) Therefore, it's O(n log n)

But I can't figure out why? I struggle to figure the last row where we use recursion, I know that it's cutting the length of the list in half each time so its O(log n), but it add's to each iteration the other recursion which is also O(log n) each time so I though its O(log n log n) but unfortunately its not.

O(log n) + O(log n) = O(log n)

Adding a print statement or two to this should help a lot:

def foo(x):
    n = len(x)
    print(x)
    if n <= 1:
        print("return")    
        return 17
    return foo(x[:n//2]) + foo(x[n//2:])

>>> foo([1,2,3,4,5,6,7,8])
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4]
[1, 2]
[1]
Return
[2]
Return
[3, 4]
[3]
Return
[4]
Return
[5, 6, 7, 8]
[5, 6]
[5]
Return
[6]
Return
[7, 8]
[7]
Return
[8]
Return

This is obviously returning once for each element in the list, which makes it at least O(n). Additionally, to split the list in a bisection search type approach takes O(log n)

def foo(x):
   n = len(x) # outer
   if n <= 1: # inner
     return 17 # inner
   return foo(x[:n//2]) + foo(x[n//2:]) #outer

we can split the function into 2 parts. The first, outer part can be defined with "n=len(x)" and "return foo(x[:n//2]) + foo(x[n//2:])" in which "x" is divided into 2 recursively. Thus, the outer function was log n. In the second, inner part is composed of "if n <= 1: \ return 17" where n is searched with "n <= 1". therefore inner part function is just n. The inner part x the outer part give us "n.log n " as a result.