34-10 Algorithms for Data Science - Linear vs Constant assessment

Hi there,

I’m currently going through the Algorithms for DS course (part of Data Structures and Algorithms topic in the DS path) and I’ve stumbled upon what I think is an incorrect answer.

In part 10 (Some Other Algorithms), three functions are provided are we are to assess their time complexity. I would argue that the correct answers are:

  1. length_time_complexity = “linear” (function with element enumeration)
  2. is_empty_1_complexity = “constant” (function implements length())
  3. is_empty_2_complexity = “linear” (again, function with element enumeration)

However, the answer provided by DQ has the latter two answers switched (i.e. is_empty_1 claimed to be linear and is_empty_2 constant).

Anybody care to discuss why an enumeration would be of constant complexity :)?

Best regards,
Tom

1 Like

Hi @mrbattle,

The is_empty_1 function relies on this function to find the length.

def length(ls):
    count = 0
    for elem in ls:
        count = count + 1

Therefore, it’s not constant. Time taken depends on the length of the data.

However, in the case of this function:

def is_empty_2(ls):
    for element in ls:
        return False
    return True

It just checks the first element and returns either True or False instead of checking all the elements in ls. Therefore, it is constant.

Hope this helps :slightly_smiling_face:

Best,
Sahil

1 Like

Hi @Sahil,

oh my, seems I should start paying more attention. Thought is_empty_1() was utilizing len() and not the custom function from the exercise.

Nice catch, thanks for the swift response :slight_smile:

BR,
Tom

2 Likes

Hi @mrbattle,

Just for clarification. Even if we were using Python’s len() function it would be linear because even with len() function, the time taken depends on the length of the iterable (list, tuple, dictionary, etc).

Here is an example:

Best,
Sahil

Hi @Sahil,

from my understanding, the len() function in Python should essentially invoke the length property of a native object (as claimed by several people here [https://stackoverflow.com/questions/1115313/cost-of-len-function]). I’ve checked in PyCharm and I’m getting results consistent with these claims.

Could you try declaring both lists as variables in a separate notebook cell and then just time the individual run of len()?

BR,
Tom

1 Like

Hi @mrbattle,

My bad! You are right about that. len() function is constant because it’s just retrieving a stored value.

This answer explains it wonderfully:

len is an O(1) because in your RAM, lists are stored as tables (series of contiguous addresses). To know when the table stops the computer needs two things : length and start point. That is why len() is a O(1), the computer stores the value, so it just needs to look it up.
https://www.reddit.com/r/learnpython/comments/752zbp/why_is_the_complexity_of_lenlist_o1/do3izyy/

Thank you for improving my understanding of how the len() function works.

Best,
Sahil

1 Like

@Sahil,

thanks goes out to you for all the amazing support!

All the best,
Tom

1 Like

That was tricky :sweat_smile:

1 Like