The first lecture of week 4 was about proving recursive functions which was accompanied by a proof of the Fibonacci Sequence. This was interesting because the Fibonacci sequence had appeared in so many courses before (and I'm guessing there is more to come) yet a formal proof was never given. In the second lecture of the week we talked more about recursive functions as well as their time complexities. We also started looking at the Recursive Binary Search function and analyzed its time complexity. I think that the approximate time complexity for the recBinSearch(x,A,b,e) is :
T(n) = (e-b)*4 + T(1)
1 comment:
It's in big-Oh of lg(n).
Post a Comment