How does iterative deepening affect time complexity?

Question

I have a tree traversal algorithm which generally operates in O(b^m) where b is the branching factor and m is the max depth.

Using iterative deepening, this algorithm is run over and over again, m times at increasing depth:

O(b^m) = b⁰ + b¹ + b² + ... + b^m

Based on my limited understanding of time complexity, we take the largest element because that is the most significant one over time, and so that element would be b^m, where m is the max depth reached.

So, with that knowledge I would conclude that the iterative deepening algorithm also runs in O(b^m).

However I have trouble understanding, from a logical standpoint, how the tree traversal could have the exact same time complexity whether the algorithm is run once at depth m, or m times up until depth m.

b^m is inherently less than Σ_k=0,..,mb^k. Therefore shouldn't the time complexity on iterative deepening be higher?

Or is there something I don't understand?

Answer 1

Basically you're asking why the following two functions have the same time complexity in terms of big O (as they're both O(n^m)):

• n^0 + n^1 + n^2 + ... + n^m
• n^m

The reason is that, at some point, for values of n and m the term n^m dwarfs all the other terms of these functions. As the input grows the runtime of the function as a whole will be determined by n^m.

Even if you come up with a function that takes n^m + 1000000000000 then at some point n^m will still be the deciding term in how long it takes to run. In other words, the runtime of both functions is bounded by a function with the term n^m times some constant.

In your example, running tree traversal once at depth m or running it m times up until depth m have the same time complexity because, as the tree grows, the runtime of running at depth m dwarfs all the other runs. Looking at how long it takes to run at depth m is basically all that is needed to find a function that bounds the runtime of both tasks.

To give another example, we can think of two functions that are both O(n):

• f1(n) = 1000000000n + 5
• f2(n) = 3n

It may seem that f1 does more work as n grows so it's not "fair" to say both are O(n). But their time complexity is bounded by a linear function: for some (large) constant c I can say that the runtime of both functions will be below f(n) = cn and thus the time complexity as a whole is O(n).