time complexity

Question

are there any resources that you advice to get more in depth understanding of time complexity analysis farther than the explanation of the concept and or digram built on the actual execution time of the code for various inputs,

i want build the skill to deal with recursive functions time complexity analysis with different types of data like lists and dictionaries with different conditions here are some examples of resources i used
https://www.youtube.com/watch?

v=6aDHWSNKlVw&t=1480s&pp=ygUgdGltZSBjb21wbGV4aXR5IG9mIHRoZSBhbGdvcml0aG0%3D
https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/i find the answer in the link directly under especially helpful yet such formality is something that i could not find resources to build i dont actually need this much formality yet for particular uneasy to determine algorithms such approach is useful since the rest can be guessed easily in retrospect

https://stackoverflow.com/questions/2709106/time-complexity-of-a-recursive-algorithm

https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/

https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

for example for this i made the guess of o(log(n)) since it is pretty similar to the binary search when the length of the list provided is large ,(have not made a formal proof or checked with a digram but this is what i found for now)

def f(lst):
if len(lst) <= 1:
return 1
mid = len(lst)//2
return len(lst) + f(lst[:mid])

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

Answer 4

Naïvely thinking you are correct. By halving the size of the problem you should end up with a logarithmic time complexity. That gives you an Ansatz for a thorough proof.

If you were to write it down you will see that the time complexity depends on both the function len on a list (supposedly O(1)) and slicing the list. The latter runtime behaviour, i can imagine, will depend on the starting and ending positions as well as step size and length. Unless you know those complexities you wont be able to say anything particular about you function f.

Answer 5

BroFar i certainly feel like both of the answers are helpful but diffrent from what i am looking for ,
I can understand the time complexity concept and how we compare preformance for large sets of data and seeing how it grows at infinity if it is exponential growth , linear etc
I also used the thing you gave to write a file that has the input as a key and run time as value and drew a digram to see the type of growth , yet when the growth type is not easy to guess such method takes a long time like 2 days min for getting a somewhat acceptable digram , so i am looking for a resource to understand how to deal with such anylsis types

Answer 6

@Ani jona
i am treating len as n and calculating for a very large input (list) , i will try to write a proper proof on paper to check the intution , and recheck the output with a digram , i am practining on some diffrent recursive problems and trying to use lists and sometimes dictionaries to build intuition but some of them endup with 2^n and n! as guesses so doing a run for n =10000 to check is not really a good idea , i searched for resources but they overlap in examples and do not use recursion much outside of Fibonacci and power functions, i may need to change the prompt of the question to a more direct one ,the answers still make sense to it thankfully