Complexity does not match actual growth in running time? (python)

Question

I ran 2 codes in python then measured the time it took to complete.The codes are quite simple , just recursive maximums. Here it is: 1.

def max22(L, left, right):
  if(left>=right):
    return L[int(left)]
  k = max22(L,left,(left+right-1)//2)
  p = max22(L, (right+left+1)//2,right)
  return max(k,p)


def max_list22(L):
  return max22(L,0,len(L)-1)

---

def max2(L):
  if len(L)==1:
    return L[0]
  l = max2(L[:len(L)//2])
  r = max2(L[len(L)//2:])
  return max(l,r)

---

The first one should run (imo) in O(logn), and the second one in O(n*logn). However, I measured the running time for n=1000 , n=2000 and n=4000, And somehow the growth for both of the algorithms seems to be linear! How is this possible? Did I get the complexity wrong, or is it okay? Thanks.

Answer 1

The first algorithms is not O(log n) because it checks value of each element. It may be shown that it is O(n)

As for the second, possibly you just couldn't notice difference between n and nlogn on such small scales.