What's the time complexity of this algorithm (pseudo code)?

Question

Assume the tree T is a binary tree.

Algorithm computeDepths(node, depth)

Input: node and its depth. For all depths, call with computeDepths(T.root, 0)

Output: depths of all the nodes of T

if node != null

depth ← node.depth

computeDepths(node.left, depth + 1)

computeDepths(node.right, depth + 1)

return depth

end if

I ran it on paper with a full and complete binary tree containing 7 elements, but I still can't put my head around what time complexity it is. If I had to guess, I'd say it's O(n*log n).

Every node gets visited, so regardless of the structure of the tree, for n nodes, the algorithm (as written) does work proportional to n. So I'd call it O(n). But the algorithm doesn't make sense; the value of depth passed into the algorithm is ignored. — Ted Hopp
@TedHopp I took out the depth ← node.depth from my pseudocode. It seemed redundant. Should be ok now, right? — Vartan

justhalf justhalf · Accepted Answer · 2016-11-25T02:50:21

It is O(n)

To get an idea on the time complexity, we need to find out the amount of work done by the algorithm, compared with the size of the input. In this algorithm, the work done per function call is constant (only assigning a given value to a variable). So let's count how many times the function is called.

The first time the function is called, it's called on the root.

Then for any subsequent calls, the function checks if the node is null, if it is not null, it set the depth accordingly and set the depths of its children. Then this is done recursively.

Now note that the function is called once per node in the tree, plus two times the number of leaves. In a binary tree, the number of leaves is n/2 (rounded up), so the total number of function calls is:

n + 2*(n/2) = 2n

So this is the amount of work done by the algorithm. And so the time complexity is O(n).

What's the time complexity of this algorithm (pseudo code)?

1 Answers

It is O(n)