Week Nine - Binary Search Tree and Big O

Week Nine -  Binary Search Tree and Big O 

This week I started to work on assignment two, part two with my partner. Although we have worked out a solution for all_regex_permutations, it was very inefficient as the size of the string grows larger. It can take upto minutes to run the method. I think to improve that method will be my main goal in CSC148 this week.

Speaking of efficiency, we also talked a little about efficiency, runtime and Big O in the lecture. The process time of an algorithm can be described using big O notation. For example, if an algorithms has a linear running time with respect to the size of the input, we can express this as O(n). (we normally would consider a very large input size to observe the runtime. Because in real-world problems, input size are normally fairly big. That is also the constant and breakpoint in the big O definition considered for). An example of the O(n) algorithm can be a linear search algorithm. There are other types of running time, for example, the following will be an example of having O(n^2)
for i in len(L):
     for j in len(L):
          a  = i * j
Or binary search, which will be an example of O(lg n). However, in some recursive functions the running time can increase exponentially or even factorially. (you really want to avoid this for larger input. I used several recursion method to do the all_regex_permutations, that is why it tooks so long to calculate). We looked at selection sort this week, I am really excited to more efficient sorting algorithm like merge sort this week. 

We also talked about binary search tree this week. We even did a lab on it to enhance the understanding. I personally found the lab pretty easy and straight forward. In some method, it is possible to use the characteristics of a binary search tree to make the method more efficient. Because in binary search trees, the first children contains all the object smaller than the root while the second children contains all the object larger than the root. Using this characteristics, many unnecessary comparison can be avoided.