educative.io

Time complexity calculation for maze question

Courses
,
#1

Hi,
I believe the time complexity of the graphs maze-that-lead-to-same-room question is incorrect.
Iterating the the corridors array of size E (number of edges) indeed takes O(E).
But then, for every two rooms, we need to find the intersection. so the neighboring set needs to be iterated in this step. The size of the neighbors set may reach O(V) worst case (V-1 to be exact, if all rooms have a corridor to to that room). Thus I believe the runtime should be O(E*V).

#2

Hi @Naama_Zuessman,

Thanks a lot for pointing it out. We’ve fixed the time complexity, and the changes will go live soon.
If you have any other query, please feel free to reach out to us.

Happy learning!

1 Like