Query regarding Time Complexity

#1

Hello,

What would the time complexity be for application of BFS and DFS in this question?

As per my understanding, DFS would be O(2^n) and BFS would be O(nm) where n and m are number of row and column for the grid.

#2

Hey @sabihash

It would be (m*n) for both bfs and dfs

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

I see, thank you. Would the time complexity for BFS and DFS when adjacency matrix is used always be O(V^2) ? In cases where adjacency matrix is not used, will it be O(V+E) then?

#5

Hey @sabihash
Yes correct
when we use adj matrix its V^2
And in case of adj list its O(V+E)

#6

Great, Thank you for the clarification

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.