Expected running time

Just ask my running time big O over this function

  int Tree: numOfNodes(){ return CountNodes( root ); }

  int CountNodes( Tree * tree ){ 
        if( tree == NULL ) return 0;
            return CountNodes( tree->left ) + CountNodes( tree->right ) + 1;
how to define the big o notation for this?
no ppl can help me d?
If you're after the algorithmic complexity of your function, rather than the actual running time, then this might help?

Big-Oh for Recursive Functions: Recurrence Relations

You haven't show the definition of Tree, but from the presence of tree->left and tree->right, I'm inferring this is a binary tree of some sort.

For a binary tree, big O should be:
O(log n)
It visits all the nodes so it is not O(log n).
Last edited on
so u guys think hats is the answer?
it's visit all the nodes
We have not given you the answer in big O notation like you asked for. I'm not going to give it to you because it looks like homework but if you know that it visits all the nodes once it shouldn't be hard to figure out.
it's is not an homework . example

to determine the big o for my understanding.
just choose the upper Big O and take its as my complexity

i just want to know since it's not an while loop or for loop.
and i can't really get it how to determine the Big O
the recursive function i search at google

it's O( n . log n )
i might add that the runtime of this algorithm isn't all depending on the complexity,
the algorithm contains a lot of function calls, this will cause considerable overhead.
Topic archived. No new replies allowed.