Time Complexity

Today's class was certainly my favorite hour of compsci, and I'm starting to appreciate how well Danny teaches #-1. We searched for and proved a bound on Recursive Binary Search, and I learned to appreciate - in awe - of how it all worked out. It was the intersection of intuition (trying to feel for a bound, which is like a guessing game), functional analysis (forming T(n), the time complexity for an array of size n), and proofs (which always ended up fitting in proving the function T(n) like a final piece in a puzzle, but over and over) - so basically the intersection of all mathematical things I like. What was amazing about the search for a bound was that much of the estimation could be proved through function generalisation, then in a (relatively #-4) deep mathematical detail.

Furthermore, we can immediately see the use of finding and proving bounds in our code. #0

In the creation of T(n): [If n = 1: 1. Otherwise: 1 + max(T(m - b + 1), T(e - m)).],  just the presence of b, e, and m to try to show T(n) is bounded by log(n) seems a long stretch, but Danny showed us that the steps involved were:
- Examination of the recursive function: n = e - b + 1 (acc to the inputs of recBinSearch(x, A, b, e)) versus m - b + 1 and e - m, i.e. examination of the call of recBinSearch with its original inputs and the call of its split lists, in order to rewrite m - b + 1 and e - m each in terms of n #1.
- Simplifying T(n) in terms of only the variable n.
- (Assuming that we prove that T is increasing and monotonic in order to simplify T(n)) Showing that if for some k in the positive integers, n = 2^k (this equation formed from our intuitive guess of the algorithm taking log n time), then we can generalise T(n) through induction as the recursive function keeps recursing. The end result is that T(n) = log(n) + 1 = approx. c*log(n) (c being a constant, which can replace + 1 since k is a positive int). #2
- Then using (complete, in this case) induction, we can show the bound holds (theta bounded, in fact) by c*log(n).

I want to master this #-6.

#0: As per usual, everywhere that is log(n) n this blog is in fact log(n)/log(2), but I strongly believe that the "2" should still be written as a subscript. It was once drilled into us that the natural numbers include 0, and that worked out well. Now that I am practicing more algorithms, I hope to get used to this mindset more often as well (TBH, it's a bit cocky for compsci to not write in these things, because they are distinct mathematical objects without writing in these details - the same goes for how there is a list of assumptions the program expects you to know beforehand #-2, but that belongs in another post #-3).

#1: This step took good thought in terms of using the floor/ceiling rules (which was so jexy), which I now remember is the the third most thing I fear, but which I also remember I started to really enjoy last semester. We'll see how things go. I need a list of the rules!

#2: I'm trying to find out what kind of math this generalisation is. Of course many fields of math are about generalisation, but where is this kind... of functional analysis (is that it)? Or convergence and limits to reach a convergence point? It is so absolutely addicting! Then there is graphical analysis to find out how the "bound" or convergence point acts compared to other functions. At least I can trust it to be in this course.

#-1: Most everyone will agree with me that at least for this class, he taught well (regardless of whether one thinks this post "sucks up", because, mind you, that will never be my intent). His analogies were absolutely spot on, and he gave them in nearly every part of proving the time complexity. We studied the same thing in CSC165 (at least I think so), but the prof didn't have much time at all to explain what we were trying to prove and how induction related to it at all. But really, the proof today was so Ihzp55Cuo7M.

#-2: I'm not talking about the math prereqs - those were useful.

#-3: I also want to post about what my syntax for a program would be, but I shouldn't be so cocky without having taken a theory course of prog languages (it's just that the previous syntax looks horrible... and takes away from clarity).

#-4: Relatively somewhat... doesn't matter, I love it. I'd post this proof on my wall if the paint didn't get stuck and if I didn't feel so much of a hipster atm.

#-5: Do you think I should have hidden in binary first? Google is too good and binary

#-6: I predict at least 40% of people will have this in their blog.