Time complexity of level order traversal in graph

Question

time complexity: O(n) can anyone explain the time complexity as O(n) in mathematical. i can find that while loop is O(logn)

public:
    vector<vector<int>> levelOrder(Node* root) {
        if(!root) return vector<vector<int>>{};
        queue<Node*> q;
        q.push(root);
        vector<vector<int>> res;
        
        while(!q.empty()){
            //BFS traversal
            int size= q.size();
            vector<int> level;
            
            for(int i= 0; i< size; i++){
                auto tmp= q.front(); q.pop();
                level.push_back(tmp->val);
                for(auto n: tmp->children)
                    q.push(n);
            }
            res.push_back(level);
        }
        return res;
    }
}

Answer 1

Well you visit each node one and only one time, so the complexity here will be O(n). This problem is not a "divide to conquer" algorithm, because wou will eventually visit all of the branches of a node (in a dichotomic algorithm, you visit only one branch).

EDIT

Complexity of recursiv algorithms can be really tricky. This formula can help you : when you have T(n) your time complexity,

T(n) = aT(n/b) + f(n).

If f(n) = Θ(n^d), where d ≥ 0, then

• T(n) = Θ(n^d) if a < b^d
• T(n) = Θ(n^d*log(n)) if a = b^d
• T(n) = Θ(n^log_b(a)) if a > b^d

in your case, f(n) = Θ(1), because you do nothing at a node, so d=0. You also have a=b>1 in general, so you are in the third case. Log_b(a) = 1, because b=a, so your complexity is Θ(n¹).