I want to ask a question about course 2008 fall .The question is in Set 6 problem #3.
"Next, change the implementation of is_valid_word to take as an argument the representation you created above rather than the word_list itself. Remember that the choice of representation can have a big impact on performance. This modification will improve the complexity of is_valid_word from O(len(word_list)) to O(1)." I can't understand how can we fulfill this change and do not know why it changes the complexity to O(1).

Question

I want to ask a question about course 2008 fall .The question is in Set 6 problem #3.
"Next, change the implementation of is_valid_word to take as an argument the representation you created above rather than the word_list itself. Remember that the choice of representation can have a big impact on performance. This modification will improve the complexity of is_valid_word from O(len(word_list)) to O(1)." I can't understand how can we fulfill this change and do not know why it changes the complexity to O(1).

anonymous · Answer

The pdf's link is here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset6.pdf

anonymous · Answer

how did you implement is_valid_word using word_list? why is its complexity O(len(word_list))? how will you implement is_valid_word with the new representation of the wordlist? http://wiki.python.org/moin/TimeComplexity