CODEWITHSUNDEEP
graphdepth-first-searchspace-complexity
Saurabh Raj
Saurabh Raj

Reputation: 65

How can DFS algorithm space complexity be nlogn?

I don't know, where had I heard that the space complexity of DFS algorithm is nlogn. n are the number of vertices. I have seen the space complexity as O(height of tree), but never heard about nlogn in case of dfs algorithm. Can someone clarify me if such type of implementation exists? if yes then how?

Upvotes: 1

Views: 392

Answers (1)

radof
radof

Reputation: 611

There isn't a single definition of space complexity which depends on the model of computation, see for example, a discussion of models. Also there might be an implementation that is worse than the optimal one for the given problem in terms of the space, but the space complexity of O(nlogn) arises naturally if you take the size of the (binary) encoding of the vertices into account as follows.

Since you have n vertices, in order to remember the current state of DFS in common implementations (in the worst case) you store O(n) vertex labels each of size O(log n). For example, if your graph has 1 billion of vertices, a vertex occupies 32 bits of memory and this number grows to infinity with the size of the graph, but such considerations are rather theoretical.

Treating vertex labels as numbers rather than strings it is a common practice to assume that each of them occupies O(1) space, see e.g., Why are strings' space complexity O(n) but numbers are O(1)?

Upvotes: 1

Related Questions