34-10 Function Time Complexity

Q&A DQ Courses
#1

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"
Doubt in Constant and Linear time algorithm
#2

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:

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

More specifically, please reply with the steps for:

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

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.

#4

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
#5

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.

#6

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