How to analyze the running time of a recursive function!?

[Roger_2]

i have created a recursive method that returns the size of a binary search tree, i would like to analyze the running time of my implementation but i dont know how.
I know the best case is O(1) if node is null but what about worst case? my researches online offer conflicting information. One source says to imagine the internal stack which makes me believe O(N^2) and another says to break it up into an equation. I feel like the worst case is O(N) as each of the nodes must be accessed in order to return their value but i have no evidence to support my claim. Any insight would be greatly appreciated. My method is below:

private int rSize(Node node){ //traverses through each left then right node and returns the size count
    if(node==null){
        return 0;
    }
    else{ 
        return (rSize(node.left) + rSize(node.right) + 1);
    }
}

[JamesCherrill]

You need to access each node once, so O(n).
The size of the stack is O(log n) so you can ignore that when there's a O(n) component

[Gribouillis]

For a tree with N nodes, the function will be called exactly 2N+1 times in my opinion (N times with a real node and N+1 times with a null node). You can prove this by induction on N by adding a leaf to a tree or by using the induction hypothesis on each of the two subtrees.

[Teme64]

JamesCherrill is correct about O(N).

Worst case happens when a binary tree with N nodes is fully biased to left (or right). In your code, null check is always same, that is, it takes a constant time and therefore recursive call to rSize(node.right) takes a constant time. Recursive call rSize(node.left) (or rSize(node.right)) traverses to the "bottom node" i.e. that makes it O(N) to reach the leaf node. You can ignore constant values mentioned above because they are just some constant value c and O(cN) is equal to O(N).

The best case with N nodes is not O(1). You have the "fastest" binary search tree when N nodes are evenly distributed. That means that the height of the binary search three is as small as possible. In this case, to traverse from root node to any leaf node takes O(log N) time because O(log N) is also the height of the binary tree.

HTH

[Gribouillis]

Nevertheless, 2N+1 calls exactly is a more precise result than O(N). There is no best case or worst case in this function in terms of number of calls. There is a best and worst case in terms of the length of the stack, but it is another question.

[JamesCherrill]

Binary search is the subject of another post by OP, but this one is about simply counting all the nodes, so let's not get distracted. Gribouillis is right, although I think the precision of the calculation is not an issue - as long as it's of the form aN+b then the answer is O(N).

[Mickey_2]

If the question is not about theoretical omega values but actual runtime on a specific system, then maybe the

timeit 

module could help.

[JamesCherrill]

Well, no, it's not about actual runtime, so what is the relevance?
There's no "timeit module" in standard Java AFAIK, and you give no link or reference for it, so what's the point?

[Mickey_2]

Sorry, I misunderstood. Feel free to delete my reply.