BFS versus DFS for random targets in ordered trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916197813977088 |
|---|---|
| author | Dimitrov, Stoyan Minchev, Martin Zhuang, Yan |
| author_facet | Dimitrov, Stoyan Minchev, Martin Zhuang, Yan |
| contents | Consider a search from the root of an ordered tree with $n$ edges to some target node at a fixed distance $\ell$ from that root. We compare the average time complexity of the breadth-first search (BFS) and depth-first search (DFS) algorithms, when the target node is selected uniformly at random among all nodes at level $\ell$ in the ordered trees with $n$ edges. Intuition suggests that BFS should have better average performance when $\ell$ is small, while DFS must have an advantage when $\ell$ is large. But where exactly is the threshold, as a function of $n$, and is it unique? We obtain explicit formulas for the expected number of steps of both BFS and DFS, by using results on the occupation measure of Brownian excursions, as well as a combinatorial proof of an identity related to lattice paths. This allows us to show that there exists a unique constant $λ\approx 0.789004$, such that in expectation BFS is asymptotically faster than DFS if and only if $\ell\leq λ\sqrt{n}$. Furthermore, we find the asymptotic average time complexity of BFS in the given setting for any class of Galton$\unicode{x2013}$Watson trees, including binary trees and ordered trees. Finally, we introduce the truncated DFS algorithm, which performs better than both BFS and DFS when $\ell$ is known in advance, and we find a formula evaluating the average time complexity of this algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05664 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | BFS versus DFS for random targets in ordered trees Dimitrov, Stoyan Minchev, Martin Zhuang, Yan Data Structures and Algorithms Discrete Mathematics Combinatorics Probability Primary: 68Q25, Secondary: 05A15, 05A16, 05C05, 05C30, 60C05, 68P10, 68R05 Consider a search from the root of an ordered tree with $n$ edges to some target node at a fixed distance $\ell$ from that root. We compare the average time complexity of the breadth-first search (BFS) and depth-first search (DFS) algorithms, when the target node is selected uniformly at random among all nodes at level $\ell$ in the ordered trees with $n$ edges. Intuition suggests that BFS should have better average performance when $\ell$ is small, while DFS must have an advantage when $\ell$ is large. But where exactly is the threshold, as a function of $n$, and is it unique? We obtain explicit formulas for the expected number of steps of both BFS and DFS, by using results on the occupation measure of Brownian excursions, as well as a combinatorial proof of an identity related to lattice paths. This allows us to show that there exists a unique constant $λ\approx 0.789004$, such that in expectation BFS is asymptotically faster than DFS if and only if $\ell\leq λ\sqrt{n}$. Furthermore, we find the asymptotic average time complexity of BFS in the given setting for any class of Galton$\unicode{x2013}$Watson trees, including binary trees and ordered trees. Finally, we introduce the truncated DFS algorithm, which performs better than both BFS and DFS when $\ell$ is known in advance, and we find a formula evaluating the average time complexity of this algorithm. |
| title | BFS versus DFS for random targets in ordered trees |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Probability Primary: 68Q25, Secondary: 05A15, 05A16, 05C05, 05C30, 60C05, 68P10, 68R05 |
| url | https://arxiv.org/abs/2404.05664 |