How to find the running time of these two functions?

Question

I'm familiar with the big O notation and the running time and most of the time I can recognize the running time of an algorithm but I'm not sure with this one. I'm dealing with a tree here.

First method:

static boolean containsData(TreeNode treeRoot, String data) {
    if(treeRoot == null)
        return false;
    if(data.equals(treeRoot.data))
        return (true);
    else if((data.compareTo(treeRoot.data))<0)
        return(containsData(treeRoot.left, data));
    else
        return(containsData(treeRoot.right, data));
}

Second method:

static boolean containsData2(TreeNode treeRoot,String data){
    if (treeRoot != null) {
        if (treeRoot.data.contains(data)) {
            return true;
        } else {
            return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 
        }
    }
    return false;   
}

I would say that both methods are O(n) I can not see how one of them would be O(log(n)).

Answer 1

Both methods have a worst case running time of O(n) if the tree is not balanced.

The first would run in O(log n) if the tree is balanced.

The second method would still need O(n) even for balanced tree since it traverses both subtrees if the record is found in the right half. It actually does a full scan of all records in sorting order until the record is found. The actual run time depends on the size of the record. A small record will be found faster, a large record will need O(n). The average is O(n).

Answer 2

Both of these methods essentially do the same thing, which is traverse the tree looking for a certain item. Both methods go left or right in search for the item, and keep doing so until reaching the end of the tree. As @Sumeet already mentioned, we can't really give you an exact Big-O running time, because we don't know whether the trees are balanced. In the case of balanced binary trees, the search time for both methods should be O(lgn). However, in the case of a maximally unbalanced tree, both the height and number of elements would be n, and therefore the search time would be O(n). If you can clarify the types of trees, we might be able to narrow down an exact running time.