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:
- length_time_complexity = “linear” (function with element enumeration)
- is_empty_1_complexity = “constant” (function implements length())
- 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 :)?
is_empty_1 function relies on this function to find the length.
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:
for element in ls:
It just checks the first element and returns either
False instead of checking all the elements in
ls. Therefore, it is constant.
Hope this helps
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
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:
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()?
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.
Thank you for improving my understanding of how the
len() function works.
thanks goes out to you for all the amazing support!
All the best,