CODEWITHSUNDEEP
javascriptalgorithmbig-o
Viet
Viet

Reputation: 6943

Does this algorithm have time and space complexity O(n) or O(1)?

Update: - Wikipedia says o(n) not O(n) so this algorithm isn't an in-place solution. - Debating whether this solution runs in O(n) or O(1).

This is my solution for LeetCode question Flatten Binary Tree to Linked List. In terms of time and space complexity analysis, I'm not quite sure it's O(1) according to some explanations. I think it's O(n) because of the use of the stack. Is my analysis correct?

According to Wikipedia, O(n) is still accepted as in-place.

More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in o(n) is allowed.

/**
 * Function flattens a binary tree.
 * Time = O(n) because we iterate through all nodes.
 * Space = O(n) because we use a stack.
 * @param {root} root Input tree.
 */
var flatten = function(root) {
    // If reach end of leaf node, return.
    if (root === null) return;

    let stack = [];
    let currentNode = root;

    while (true) {
        // Push right branch to stack first,
        if (currentNode.right) stack.push(currentNode.right);
        // then left branch.
        if (currentNode.left) stack.push(currentNode.left);
        // If there are branches in stack:
        if (stack.length > 0) {
            // Change the current currentNode right branch to the last element of the stack:
            currentNode.right = stack.pop();
            // Change left branch to null
            currentNode.left = null;
            // Advance by changing current currentNode to the right currentNode.
            currentNode = currentNode.right;
        }
        else break;
    }
}

Upvotes: 0

Views: 233

Answers (1)

walnut
walnut

Reputation: 22152

Yes, the algorithm uses Theta(N) worst-case time and worst-case additional space where N is the number of nodes in the tree. The time complexity is is clear, because you push and pop each node once.

The space complexity is a bit more tricky, but consider for example a tree that is a list where the next elements of the list are the left children, but assume it has additionally for each of these list nodes one right child which itself does not have any children.

With that example your algorithm will walk through the left-hand nodes, adding the right-hand ones to the stack, but only popping those once the end of the original list is reached, i.e. there will be about N/2 elements in the stack.

Best-case, the time complexity is still Theta(N), because you always iterate over all nodes, but the best-case space complexity is Theta(1), because e.g. a tree that is already a list will never increase the stack size to more than 1.

This would usually not be considered an in-place algorithm, because it uses additional Theta(N) space, at least worst-case. As explained in the Wikipedia article, an in-place algorithm should require o(N) additional space or, I would say, usually only O(1) or slightly more than that, e.g. O((ln N)^k) for some k maximum. Whether one should count worst-case or average-case is another question.

o(N) is the little-o notation, not the big-O notation. It means the the time/space is asymptotically smaller than c*N for every c > 0. Theta(N) is therefore never o(N).

Also, Theta(N) means that not only is it O(N), meaning asymptotically smaller then c*N for some c > 0, but also that it is asymptotically larger than c*N for some c.

If you want an in-place algorithm by the stricter definition, you should not require any additional container of dynamic size.

Upvotes: 3

Related Questions