Binary Tree Multithreaded Time Complexity

Question

Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then wouldn't the big O time complexity be O(log n). I was under the impression that you could never traverse an entire tree in less than O(n) since you'll have to search each node. However, it seems like by using multithreading, one can reduce the amount of nodes to be searched in half at each node.

Would the space complexity still be the same O(n)? Also, if the the time complexity really is O(log n), are there any optimizations that could possible make it a bit faster?

Answer 1

[..], then wouldn't the big $\mathcal{O}$ time complexity be $\mathcal{O}(\log n)$

People often forget that big-$\mathcal{O}$ notation only is meaningful in a certain context, here this becomes obvious:

You are probably used to count some set of instructions (like comparing, adding etc.) as one unit - called unit cost model - each instruction happening sequentially. In that model you're right, traversal and outputting every vertex of a binary tree is $\Omega(n)$ (ie. you cannot do better than linear).

However when talking about parallel algorithms and their complexity things change, first of all you will need to specify $p$ how many processors you use¹. You will also need to specify whether multiple processors have exclusive or concurrent access for reading/writing.

You were probably talking about the CREW (concurrent read, exclusive write) PRAM and assumed $p = n$ in your question:

you could never traverse an entire tree in less than $\mathcal{O}(n)$

In total all the processors will have looked at $\mathcal{O}(n)$ vertices in the binary tree, this does not change and is called the work.

You were right that the time complexity (refered to as depth) is $\mathcal{O}(\log n)$ for that algorithm.

---

To illustrate my point even more, assume that the binary tree is given as an array with a certain order and still using $n$ processors with a CREW machine. Now, every (numbered) machine can simply lookup the value at its position in that array.

This algorithm has still $\mathcal{O}(n)$ work, but $\mathcal{O}(1)$ depth.

Conclusion

Always be aware of the context (eg. what model, what input format) since this has a great influence on the complexity. Once you introduce parallelism things become different and it's important to be precise about what assumption you make and how many processors an algorithm uses.

---

_{1: From now on I will assume a parallel random-access machine since it's very simple but still useful.}