- #1

evinda

Gold Member

MHB

- 3,836

- 0

The following two functions are given and I want to find their time complexity.

Code:

```
function BinarySearchTreeLookUp(key K,pointer R): Type
if (R==NULL) return nill;
else if (K==R->key) return R->data;
else if (K<R->key)
return(BinarySearchTreeLookUp(K,R->LC));
else
return(BinarySearchTreeLookUp(K,R->RC));
```

Code:

```
function BinarySearchTreeLookUp(key K,pointer R): Type
P=R;
while (P!=NULL && K!=P->key){
if (K<P->key) P=P->LC;
else P=P->RC;
}
if (P!=NULL) return(P->data);
else return nill;
}
```

I think that the time complexity of the first function is $O(h)$ where $\log n \leq h \leq n-1$ and that the time complexity of the second function is $O(n)$. Am I right? (Thinking)