Can someone please explain why time complexity is O(1)


  • 0
    R

    Hi,
    my solution is just the normal one, can someone tell me why time complexity is O(1) not O(n)?

    class BSTIterator {
    public:
        BSTIterator(TreeNode *root) {
            p=root;
        }
        /** @return whether we have a next smallest number */
        bool hasNext() {
            if(p!=NULL || !s.empty()) return true;
        }
        /** @return the next smallest number */
        int next() {
            while(p){
                s.push(p);
                p=p->left;
            }
            TreeNode* next=s.top(); s.pop();
            p=next->right;
            return next->val;
        }
    private:
        stack<TreeNode*> s;
        TreeNode* p;
    };

  • 0
    M

    First of all I think your code has time complexity O(h). I have been wondering about the same question. Finally I got the answer. The key is "on average". Since you have much more nodes on the bottom of the tree than on levels close to the root, nodes on the bottom levels tend to consume only 1 or 2 operations to get to the next one.


  • 1
    R

    you can assume the BST is a completed BST with height = h.

    the count of the nodes f(h) = 2 ^ h - 1.

    assume level 1 is the root, and level h is the leaves.

    calling next() to get the value of the node in level i costs (h - i) steps.

    the total steps g(h) = 1 * 2 ^ (h - 1) + 2 * 2 ^ (h - 2) + 3 * 2 ^ (h - 3) + ... + h * 2 ^ 0

    => 2 * g(h) = 1 * 2 ^ h + 2 * 2 ^ (h - 1) + 3 * 2 ^ (h - 2) + ... + h * 2 ^ 1

    => g(h) = 2 * g(h) - g(h) = 2 ^ h + 2 ^ (h - 1) + 2 ^ (h - 2) + ... + 2 ^ 1 - h = 2 ^ (h + 1) - h - 2

    so the average step t(h) = g(h) / f(h) is almost 2, O(t(h)) = O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.