# Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

Depth-First-Search (DFS) has a quasilinear (i.e.,$$\widetilde{O}(m+n)$$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $$\widetilde{O}(m+n)$$ time algorithm in multitape Turing machine model.

• For the "linear" part, I guess no, since you need an extra-factor $O(\log n)$ to read the node IDs. – Lamine Jul 23 '19 at 15:18
• I don't care about the log factor. Quasilinear (i.e., $\widetilde{O}(m+n)$) time algorithm will be OK. – Qian Jul 24 '19 at 14:44
• You don't care about in your new edited question. The previous one, which I commented, asked for "a linear or quasilinear" algorithm. – Lamine Jul 24 '19 at 15:04