Time Complexity

The concept of time complexity was covered a few weeks ago. However, I did not want to record anything of it until I deeply understand the concept properly. Time Complexity is an quantifier of time taken of an algorithm. This is mostly used by the computer scientist to create the most efficient computer program. The chapter started with an example of recursive binary search. My first intuition about this algorithm was much focused into the code rather than the bigger picture. I had hard time to understand the lecture because I was trying to understand the code while my professor was looking at the bigger picture. From this, I learn that the detail about the codes do not really matter much in terms of time complexity. I have to look at the bigger picture where the recursion is happening and the condition of the recursion. For example, in this recursive binary search example, we assume that the array is sorted. We check the upper half recursively if the array at mid point is greater than a target. We check the bottom half recursively if the array at mid point is smaller or equal to the target. No matter how long the stopping point, the time complexity of a stopping point is one in general because only one or two lines are being executed. In order to find the big oh, the worst case, we take the maximum of the recursive functions. The maximum will return the most time taken to achieve the target given an array size.

Second thing I learned from this chapter is unwinding. Unwinding is expending or rewriting a recursive algorithm until it can be expressed as a closed form. Usually, the unwinding happens until number of steps reach the size of the input, n. The algorithm is usually simplified to a closed form, an expression in finite number rather than a recursive algorithm. When I tried the unwinding the first time, I kept expending until I found a pattern. However, this was a mistake. It is much crucial to expend to a a simplified form. For example, unwinding a Fibonacci sequence can generate a pattern of pascal's triangle;

F(n) = F(n-1) + F(n-2)

        = F(n-2) + 2F(n-3) + F(n-4)

        = F(n-3) + 3F(n-4) + 3F(n-5) + F(n-6)

        ....

It is true that there is a pattern but the pattern can hardly be implied to a closed form. Therefore, the following unwinding would be much easier to handle closed form;

F(n) = F(n-1) + F(n-2)

       = 2F(n-2) + F(n-3)

       = 3F(n-3) + 2F(n-4)

       = 5F(n-4) + 3F(n-5)

                 ....

At nth step, the first unwinding is so huge that it would be hard to compute. On the other hand, the 2nd unwinding has just two terms so it is much easier.

From this, I learn that sometimes finding a pattern is not really it. I have to think if this can be implied to a closed form. If it is impossible, I have to go back and find another pattern.