Big O help

Question

If i had a function like this...

void myfunction(node* root)
{
   for(int i = 0; i<root->children.size();i++)
   {
      myfunction(root->children[i]);
   }
}

granted thats just the part of the function I have a question on, but would that be n^2 or just n, for big O? I guess the question is if you have a for loop and inside that for loop a function call to itself, is the Big O the number of iterations times the function?

Answer 1

This is an in-order traversal of an n-tree, but you hit every element, so it's O(n) (big-theta is more appropriate).

Answer 2

In mathematics, computer science, and related fields, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation allows its users to simplify functions in order to concentrate on their growth rates: different functions with the same growth rate may be represented using the same O notation.

The rest here.
And regarding your example you definitely have O(n).

Answer 3

This is O(n), where n is the total number of nodes in the tree

Answer 4

It is a recursive function call. You shall need a bit of looking into recurrence relations to calculate the time complexity in Big O notation. Your reasoning is correct in a general case. In this specific case, the answers have already been posted.

EDIT: Refer this link for a discussion of Big-Oh for Recursive Functions.

Answer 5

You can work this out by considering what happens to a tree with N nodes.

The function will be called once for every node in the tree so is both O(N) and Big-Theta(N).

Consider how it doesn't matter how wide the tree is verses how tall the tree is for the big O value, it still has the same number of visits to make.

That said the depth versus width does affect the space considerations of the function.

If the tree is extremely wide (say the width is such that the depth is always constant for any N) then the stack space required for the traversal is constant.
If however the width was a fixed constant value > 1 then the stack space required is O(log(N)).
If you had the degenerate case where the width was 1 then the tree becomes a linked list and the space requirements are O(N).
Some languages/compilers will be able to optimize away the recursion so that the space requirements are actually constant (but this is dependent on what you are doing/returning during the traversal).