# 34-10 Function Time Complexity

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
def is_empty_1(ls):
if length(ls) == 0:
return True
else:
return False
is_empty_1_complexity = "constant"

# Check whether a list is empty -- Implementation 2
def is_empty_2(ls):
for element in ls:
return False
return True
is_empty_2_complexity = "linear"
``````

Hey, Mykola. I’ll try to nudge you towards the right direction in this answer.

• `[]`;
• ``;
• `[0,1]`;
• `[0,1,2]`;

1. `is_empty_1()`;
2. `is_empty_2([])`;
3. `is_empty_2([0, 1, 2])`;
1 Like

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 `len`, but `length` — a function defined earlier in the mission. You can check its implementation.

1 Like

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 `for` loop.

Exactly!{{{{{}}}}}