Doubt in Constant and Linear time algorithm

I am confused with the answer provided while solving the course Algorithms-section10. According to my understanding, when we need to check each element in a list, then it takes ‘linear’ time, which is the case for Implementation 2.

For Implementation 1, the algorithm is just checking the length of the list, so the correct answer should be

is_empty_1_complexity = "constant"
is_empty_2_complexity = "linear"

However…the given answer is :

is_empty_1_complexity = "linear"
is_empty_2_complexity = "constant"

Here are the implementations.

# Check whether a list is empty -- Implementation 1
def is_empty_1(ls):
    if length(ls) == 0:
        return True
        return False
is_empty_1_complexity = ""

# 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 = ""

Could you please clarify ?



Hey, Tapasi.

I believe your question has been adequately answered in the following two topics:

Hey Bruno,
Thank you for pointing out the answers. Understood perfectly.