Time Complexity

Now it is in week 6, half of the fall semester! Wow, time is so fast!

Course topic now is about Time Complexity. This is very similar to what I learnt in CSC165. But since I did not understand time complexity well in CSC165, I listened to the lecture carefully and will go to office hour to ask any questions that pops up in my mind.

We are learning complexity of recursive functions. Unwinding is a mostly used way to find the lower and upper bounds of a function. This is a different approach from how find the lower bound in CSC165. First, develop a special case and then apply for more general case, for example, first suppose n to be the power of 2 and then apply n to arbitrary numbers.

But there was one thing that I did not understand in class this week. Professor drew a picture to prove that a function was non-decreasing. I did not understand how this picture related to the decreasing of a function. So I went to the section on Thursday night. After the lecture, I asked professor Heap what did this graph mean. The professor explained patiently that since at first we supposed n to a power of 2 and this was not a general case, we wanted a more general case to apply to the unwinding. To apply the unwinding to a general case, we used the upper and lower bound of  log(n) to get an arbitrary number. First prove T was not decreasing and then used the relationship between n and n nod and the unwinding to develop an inequality that contained T(n) on one side of the unequal sign and n on the other side. In this way, we could find out both the upper bound and lower bound of a function.


After professor's Heap's explanation, I found I got a better understanding of  how to develop the upper and lower bound for a function.  Asking questions to professor helps a lot. He can always explain things well and he is very patient. ^_^