Can you explain me why this algorithm is O(n) as time complexity?

Question

class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;

Stack<Node> stack = new Stack<>();
stack.add(root);

while (!stack.empty()) {
root = stack.pop();
list.add(root.val);
for (int i = root.children.size() - 1; i >= 0; i--)
stack.add(root.children.get(i));
}

return list;
}
}

Answer 1

<DD> No, I don't think it's the correct explanation. Yes, each node is processed one time but it doesn't matter here ... I think that the behavior is linear because also with large inputs, it is still linear .. I mean what matters when we re calculating time complexities is our parameters, which change how our code behaves ... In this case, it is the number of nodes

Answer 2

<DD> I have asked for an explanation why this algorithm is O(n)/linear? You gently answered that is O(n) because each node is processed one time. From my point of view this explanation isn't correct because Big O notation is linked to the following question: How does algorithm speed scale when input scales becoming very large?

Answer 3

<DD> Thank you very much!!!