binary search tree insert complexity

[GTMi1hU5]

Could somebody please help me do a complexity analysis(deduction) of the insert algorithm of a binary search tree? I have no idea how to explain it in writing.

[keskiverto]

How does one insert into a BST?

[GTMi1hU5]

I'm doing a recursive insert:

Tree* Tree::insert(Tree* b,MyType m)
{
	if(b == NULL)
	{
		Tree* q = new Tree(m);
		return q;
	}

	if(m < b->getMyType())
	{
		b->left = insert(b->left,m);
	}
	else
	{
		b->right = insert(b->right,m);
	}

	return b;
}

where b is the current node and m the info.

[keskiverto]

How many times will the insert be called, on average, i.e. how deep are the branches in ideal case?

What is the worst case? Worst sequence of insertions? How does the tree look in that case?

[GTMi1hU5]

Let's say we call it n times. The worst case could be O(n), the best case would be Θ(1) and the average/global case would be Θ(log(2)n).

[GTMi1hU5]

Never mind. I think I know it now. It's like 1+2+2^2+...2^k = n. That sum is equal to 2^(k+1)-3, which is equal to n. 2^(k+1) = n+3, then k+1 = log(2)(n+3), then k = log(2)(n+3) - 1, which is approximately log(2)n. Thanks!