time complexity

Question

i am analysing some functions and not sure if i am doing this correctly
def f(lst):
if len(lst) <= 1:
return 1
mid = len(lst)//2
return len(lst) + f(lst[:mid])
the run time for this i assumed would be o log(N) since i have a constant c every run and each run i am calling n n/2 n/4 etc so o(log n )number of calls , am I doing this incorrectly

Answer 1

Dareen Moughrabi ,

in general, it is a good idea to have a try with google. using an appropriate prompt you will get good results.

> you can find some information about measuring execution time:
https://realpython.com/JUMP_LINK__&&__python__&&__JUMP_LINK-timer/

> if you are looking for time complexity in general, you can have a look here:
https://towardsdatascience.com/understanding-time-complexity-with-python-examples-2bda6e8158a7

Answer 2

Dareen Moughrabi imagine you are trying to figure out the best library or algorithm to use given a simple or large dataset of numbers , sum them and return the sum value in how much time.

Here is a code I created not to long ago to compare list vs array vs np.array

https://sololearn.com/compiler-playground/cWCI3vAj3grj/?ref=app

Answer 3

Lothar i actually read the link you mentioned (I like that site a lot ) , i used it in my code too but i am trying to guess worst case time complexty and can’t really translate runtime diffrence to one of the cases