CSC 148 Python Week 10 Slog: Efficiency of Algorithms

Today in class, we learnt more about Efficiency of Algorithms. Because we can solve Binary Search Tree insertion in both iterative and recursive way, the professor today want to show us which is a more efficient way. Basically, we will consider two factors in analyzing the efficiency here. The first one is how large is the extra memory of these two algorithm and the time it takes to do two algorithms. We can find out that in doing iterative way, we do not need much extra memory as the for loop will always have a constant extra memory to store. However, for recursive way, we can see that if the tree is balanced, which means that the right and left side have similar amount of children, there will still be O(lgn) larger amount of extra time than iterative way. For the time they spend, we can see that for iterative way, there will be n number of time but for recursive way it will take 2 to the power of n number of time. This means that in a Binary Search Tree inserting new value algorithm, recursive algorithm is not efficient. However, recursion is a very powerful technique for problems that are naturally recursive. So different methods will work better for different problems. 

Here is a graph of the comparison between Recursive and Iteration and I find it very helpful.