# FAQ: Asymptotic Notation: Python - HashMaps vs. Linked Lists Runtime

This community-built FAQ covers the “HashMaps vs. Linked Lists Runtime” exercise from the lesson “Asymptotic Notation: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

## FAQs on the exercise HashMaps vs. Linked Lists Runtime

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

## Join the Discussion. Help a fellow learner on their journey.

Agree with a comment or answer? Like () to up-vote the contribution!

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Checkpoint 2 in the excersise says:

hashmap_runtime = “1”

Which I believe is wrong.
Big O stands for worst case, which would be searching for a key that is not in the HashMap. In which case we end up in infinite while loop with the existing code, because:

possible_return_value != key

Always evaluates False because possible_return_value is a list and key is a string

possible_return_value is None

Always evaluates False because our HashMap is full and we have value for every index

possible_return_value[0] == key

Alwayse evaluates False because our key is not a valid key

in place of the infinite while loop we could use

for i in range(self.array_size - 1)

with this for loop in place our big O should look like this

hashmap_runtime = “N”

Is this correct?

1 Like

Once through N items will be `O(N)`, as you suspect.

1 Like

Sorry if my question was not formulated correctly. The second excersise in the lesson is asking for big O for HashMap search.

1. Through the above solution I came up with the answer “N”
2. The excersise does not accept this as correct answer and it requires answer “1” to advance to excersise 3

Which of the two is correct and is there a bug in the excersise.

1 Like

1 Like
2 Likes

I haven’t taken this course, but something just occured to me… Does it take the same amount of time to retrieve a item no matter which key we poll in the HashMap? If that is the case, then it would, I believe, be `O(1)`.

2 Likes

HashMaps use collision when assisigning key-value pairs to a list, to avoid writting different keys to same index. When collision occurs the key-value pair is written at the next list index. Without collision we will have O(1) runtime:
1)hash the key
2)compress the hash to an index
3)grab the value at index from the list

With collision we have to iterate the list so it will be O(N):
1)hash the key
2)compress the hash to index
3) if key at index matches our key return value at index
4) else add 1 to collision counter and repeat (1-3)

2 Likes

Hi
Could anyone help me understand why this code doesn’t run successfully for exercise 3 on HashMaps vs. Linked Lists Runtime:

#Get Zachary’s Disease from a Linked List
#Write Code here for Checkpoint 3
if current_value[0] == ‘Zachary’:
else:
while current.get_next_node != None:
print(current.get_next_node() != None) #this is just here to show myself that this is None on the iteration where the code fails.
if current.get_next_node().get_value()[0] == ‘Zachary’:
current = current.get_next_node()

I thought the while loop would stop before I get the error:
Traceback (most recent call last):
File “script.py”, line 40, in
if current.get_next_node().get_value()[0] == ‘Zachary’:
AttributeError: ‘NoneType’ object has no attribute ‘get_value’

Any help much appreciated!

1 Like

It makes your code much more readable if you post it using proper formatting via the </> icon in the menu at the top of the text box.

As to your question, look at these three lines:

``````while current.get_next_node != None:
print(current.get_next_node() != None)
current = current.get_next_node()
``````

Do you see anything in the second and third lines that is missing from the first?

1 Like

@patrickd314 thanks, I’ll use that formatting next time (first time posting here!)

And yes I do - that’s all working now. I can’t believe how long I stared at this without noticing that.

Thanks again!

1 Like

The HashMap of the module employs separate chaining, so big O for this HashMap’s search would not be infinite, it would be N.

However, a HashMap with O(N) isn’t much of a HashMap. That would be literally identical to employing just a Linked List. For a module comparing the runtime of a HashMap to the runtime of a Linked List, it wouldn’t be very effective if the HashMap’s hashing function boiled down to simply another Linked List.

The hashing function uses the encode() method. This will result in a very effective distribution of hash codes. On average, this will result in nearly always O(1), with some exceptions. Strictly speaking, you are correct that big O is intended to represent the worst case, but again, it’s not very meaningful to equate the runtime of a HashMap to a Linked List when the HashMap virtually never reaches the runtime of a Linked List, let alone come anywhere near it. For this purpose, we used the amortized time complexity instead, because clearly a well-designed HashMap is superior in runtime to a Linked List, and we still use big O notation despite no longer strictly representing the absolute worst case.

However, the course makes no mention of amortized time complexity, and selecting O(N) is both an honest and technically correct answer, despite being an impractical answer.

2 Likes