In the mission Algorithms we are asked to find time complexities of the two following functions. I think that function 1 has a constant time complexity (find the length of the list) and function 2 has linear time complexity (we have to iterate over all elements in the list). But this answer appears to be wrong. Is it my mistake or is it a mistake of Dataquest?:
# Check whether a list is empty -- Implementation 1
if length(ls) == 0:
is_empty_1_complexity = "constant"
# Check whether a list is empty -- Implementation 2
for element in ls:
is_empty_2_complexity = "linear"
Hey, Mykola. I’ll try to nudge you towards the right direction in this answer.
Try running each function in your head with the following inputs:
More specifically, please reply with the steps for:
is_empty_2([0, 1, 2]);
Hi, Bruno. Thank you for your hint. I see that lists have different lengths. So the second function should have a linear time complexity as I said because you iterate over each element in the list. And the first one should have a linear or constant time complexity. It depends on the implementation of the function
len(). But the answer from Dataquest says that the first function has linear and the second function has constant time complexities. I don’t understand why.
Please indulge me in my request, specify the steps of running 2. and 3.
Note that it’s not
length — a function defined earlier in the mission. You can check its implementation.
Thank you, Bruno. I was not very attentive. So because of the implementation of the function
length() the first function has linear time complexity. And of course, the second one has a constant time complexity because of the statement
return in the