1

If I had a function like this:

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

Would that be Big O of n^2 or Big O of n? 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?

DanM7
  • 2,203
  • 3
  • 28
  • 46
Bramble
  • 1,395
  • 13
  • 39
  • 55
  • 5
    Yes, I would love to do your homework for you. Thanks for asking. – Eric Jun 29 '09 at 13:48
  • There are lot of similar threads in SO: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it, http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds, http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o, etc. – vgru Jun 29 '09 at 13:48
  • It is O(n^98345984375743598734598734953752345). – San Jacinto Jun 29 '09 at 14:27

5 Answers5

9

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).

Ron Warholic
  • 9,994
  • 31
  • 47
  • 2
    New user asking a very academic question = probably homework. I hope you at least understand the fundamentals of why this is O(n). – Ron Warholic Jun 29 '09 at 13:52
  • 3
    The O(n) is correct, but it's not an in-order traversal. One could argue that it's pre-order or post-order, but there's no way to *really* tell since the function does no work at each node, it just visits them. Doing something before the for loop would be pre-order — doing something after the for loop would be post-order. – Quinn Taylor Jun 29 '09 at 14:20
  • 2
    Let's just call it a depth-first traversal. We know that much, at least :) – Brian Jun 29 '09 at 14:25
  • Ah yes, he doesn't actually do any node processing so it's impossible to tell. – Ron Warholic Jun 29 '09 at 15:47
2

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.

  • +1: In a recursive operation, esp. for a beginner, have to stop and consider what n really is. In this case, not depth, or breadth, but simply total number of tree nodes. –  Jun 29 '09 at 14:26
  • Recurrences are definitely a key tool for the analysis of recursive functions, but in this particular case it looks like he *might* have a variable number of children at each node. Constructing and solving a recurrence in that case would be pretty hairy. For this problem it's best to just think about how the function is visiting nodes as others have described. – jtb Jun 29 '09 at 18:15
2

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).

ShuggyCoUk
  • 36,004
  • 6
  • 77
  • 101
1

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).

Artem Barger
  • 40,769
  • 9
  • 59
  • 81
0

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

Samuel Carrijo
  • 17,449
  • 12
  • 49
  • 59