Please help..I believe each line should have an answer of time complexity (big-O
ID: 3856898 • Letter: P
Question
Please help..I believe each line should have an answer of time complexity (big-Oh)..or at least each section if not each line...Please explain as much as possible to help me understand.
1.
1. For each snippet below, give the time complexity (in big-Oh). If it is not possible to say, then explain why. If there is a data structure with variable size, use n to represent the size str . . print (str) for e1 in some list: for e2 in some list: print (1) for i in range(len(10)): for i in range(len (10)) print(i) x [0] * len(some-data-structure) =Explanation / Answer
str = ...; O(1) (Basically any constant operation will take time as constant which will be O(1) )
print(str); O(1)
for e1 in some_list (Let's imagine you have n elements in list 1)
for e2 in some_list (Let's imagine you have m elements in list 2)
print 1;
For each element in list 1, it will execute list 2 'm' elements. So for each element it will be 1*m. Hence for n elements it will be n*m which is nothing but O(n*m), if n==m then it would be O(n^2)
for i in range(len(10))
print i
This is also similar case of the above loops. Imagine the range(2), it would run 2 times, if it's 'n' it would run n times.
x = [0] * len(some_data_structure) constant
Even for the problem continues, it would same as explained above. Just look whether it's a single statement or inside a loop or recursive.
Single statement: always it would be constant which is O(1)
Loop: Depends on how many times the loop is running. For each time it would be O(1), so it will become n*O(1) which is nothing but O(n). Same with the recursive too.