educative.io

Wrong time complexities in Cheet sheet

Courses
,
#1

Hi team,

I could see there are many mistakes in time complexity cheet sheet. This is really not acceptable as many people will be preparing for their interviews using this material.

Mistakes i could see…

Arrays and Dynamic Arrays - given as O(1) for insertion. It has to O(n) as inserting at beginning or middle needs moving the elements.

Que: Deque is given as O(1) - it has to be O(n) as we move the elements towards front. Unless you are using linked list inside the implementation.

HashTable : Insertion and Retrival is given as O(n). But it is O(1) as we retrive the data by hashindex. It is the advantage of Hashtable.

Please correct them ASAP. And i request Educative.io to get the materials reviewed.

#2

Hello Aswini,
Let me try to answer your query. The Array time complexity would be O(1) if we insert a new value at the end of an array as no values need to be shifted then. Deque takes O(1) for a queue made from linked list implementation. Lastly, the worst case for a hash table is O(N) and the average case is O(1) as mentioned in the lesson you are referring to.
Hope this answers your query

#3

Hi Ahmed,

Thanks for replying.
I have already mentioned those scenarios in my previous comment. But in the article, it has to be mentioned correct Worstcase scenario with the specific internal datastructure used. Otherwise it will leave the user confused.

I hope you can update the article that helps the readers.

Thanks,
Aswini.Y