As you prepare for the technical interviews in the job search process there is always a lot of talk of calculating the Big O or the time and space complexity of an algorithmic solution.
For simpler solutions, it is easy to see why a for loop that loops through an array or string with length “n” would have a time complexity of O(n). The for loop has to go through “n” number of elements and therefore that would take “n” times.
When in a technical interview, after having coded out the brute force or naive solution, you are often asked to try to optimize that solution. If for example, you have two nested for loops in your solution, your time complexity will be O(n²), which is not very time efficient. You may then want to try a recursive solution, which would increase your space complexity since you will be taking up memory on the stack, but it would improve your time complexity.
One of the best time complexities to have is O(log n). It is like having a constant time, or O(1), time complexity. The beauty of balanced Binary Search Trees (BSTs) is that it takes O(log n) time to search the tree. Why is this?
With a balanced BST, we are always halving the number of elements that we look at. This is like what we would do when we are searching an alphabetized list for an entry, we decide if we want to look at the first half or the second half of the remaining elements once we decide if our target is higher or lower than the first element we look at. With an alphabetized list, if my search element were “tomato”, I would know how far back to go once I determined where the letter “m” was in the list that I had.
When searching a numerical BST we know that all the greater numbers are always to the right and all the lesser numbers are always to the left. If we determine that our search element is greater than the top node of the tree, we would then cut our search elements in half and only look at the items on the right. As we searched through the right, we would keep comparing and subsequently keep dividing our number of search elements by half.
The O(log n) that we use when talking about Big O has a base of 2. The number of elements is “n” and our time complexity would be the power to which we would raise two to in order to reach n elements. Since we are halving our number of search elements in order to find our target element, we are dividing the elements by two each time. The number of times that we need to divide our elements by two is the Big O. How many times do we need to multiply two times two in order to get to n? Our answer is (log n).
If we look at an example, we can say that our BST has 8 elements in it. If we halve it we have 4, halve it again we have 2, halve it again we have 1. Worst case scenario, our target element is that last element, which means that we had to halve our BST three times. If we look at it as an exponent, that is 2 ³. Our time complexity is O(3) or O(log n).
Since time and space complexity is always worst case scenario, the time complexity for a balanced BST is always O(log n)!
Hope that was a clear explanation!
