Week 9: Binary Search Trees and Time Complexity

This week in lecture we focused on algorithm efficiency and one of the notations used to quantify it, Big Oh. Big Oh notation is used to describe how efficient an algorithm by saying how fast it will run in the worst case scenario for an n-sized list.

One of the examples given to use to analyze Big Oh efficiency was a binary search tree, in which you can divide the tree into 2 parts because if the object you are looking for is bigger than the root, then it will be on the right side of the root, and if it is less that the root, then it will be on the left side. So for an average tree the big Oh would be O(logn) because it keeps dividing the list in half every time it searches, however in a worst case scenario the BST can be very poorly designed and have a very long chain of nodes with only one child, therefore the worst case efficiency would be O(n) because the complexity increases linearly for every item added to the list.

Algorithm performance is very important for computer scientists and programs because bad time complexities may overload a computer's processing capabilities, or simply have a function take very long to complete such as 10 minutes, then if a less complex algorithm were used to make a function complete in less than 1 second.

In many cases where the time complexity equation of a function as it depends on n such as: 7n^2 + 2n + 5, only the largest power of n will be considered for time complexity because if n is in the billions 7n^2 will be much larger than 2n or 5, therefore on 7n^2 is considered and the time complexity is O(n^2).

A binary search tree is an example of how creating certain conditions can optimize time complexity of searching through trees, as regular trees have random placement of nodes so the time complexity rises linearly but BSTs divide the list into 2 halves so that the time complexity rises logarithmically.

With my prior experience of Big Oh notation and time complexity from taking CSC165 last semester it was easy for me to understand the concepts discussed in class this week, especially since I was writing proofs for time complexity just a few months ago.

Until Next Week,
Maxim Isakov