Time Complexity of Tree Sort

1. t = makeNode(first(S)); O(1)

2. remove the first element from S; O(1)

3. for each element x in S {

insertSearchTree(t,x);

}

4.inorderTraverse(t); O(n)

Worst case:

T(n) = O(n2)

Best case:

T(n) = O(nlogn)