BFS versus DFS for random targets in ordered trees
BFS versus DFS for random targets in ordered trees

Stoyan Dimitrov, Rutgers
Fine Hall 224
We consider the average time complexity of breadthfirst search (BFS) and depthfirst search (DFS), when we have a uniformly random target node selected among all nodes at level m in all ordered trees with n edges. Intuition suggests that for a fixed n, BFS should have better average performance when m is small, while DFS must have an advantage when m is large. But where exactly is the threshold, for m as a function of n, and is it unique?
We answer this question by using results on the occupation measure of Brownian excursions and an identity related to lattice paths.
At the end we ask some interesting further questions.