Week 2 - Asymptotic Notations and Analyzing Algorithms

This week in the course of Design and Analysis of Algorithms we explored the different mathematical notations for algorithm analysis, grasp the fundamentals of how to analyze nonrecursive and recursive algorithms, and lastly we took a look at an algorithm design known as the Brute Force Algorithm. This week was quite difficult for me as I was having trouble with analyzing recursive algorithms, specifically with finding the recursive relation and the initial conditions for some of the problems within the quiz. Though I will say there were some good resources from other students in discord that provided some much needed help in that department. 

At the start of the week we reviewed the different mathematical asymptotic notations for algorithm designs which are the BigO, BigΘ, and BigΩ. The lecture videos identified how to find and distinguish between using each of the asymptotic notations. For BigO it represents the upper bound of an algorithm's run time. This means that it makes sure that the algorithm does not exceed a certain growth rate as input increases. For example in the book it identifies it as t (n) ≤ cg(n) for all n ≥ n0. In this case we can say t(n) is the algorithm's runtime, and g(n) is the comparison, it states that at some point the t(n) should not exceed that of g(n). An example is if the BigO for an algorithm is O(n log n) then it should not exceed this rate, essentially we can say that 1/2n meets the criteria for O(n log n) because it's a linear growth and much smaller than n log n. This means that any function that grows no faster than n log n can satisfy the Big O definition. For BigΩ it represents the lower bound of the runtime, this time it means the run time should not be less than a certain growth rate. Noted in the book as t (n) ≥ cg(n) for all n ≥ n0; where t(n) must grow at least as fast as g(n). For example, n log n is BigΩ of (1/2)n, because n log n grows faster than linear time and will be greater than or equal to (1/2)n. Lastly BigΘ represents the tight bound of the algorithm runtime, where time grows at the same rate in both the upper and lower bounds. The book notes it as c2-g(n) ≤ t(n) ≤ c1-g(n) for all n≥ n0. Essentially it is neither faster nor slower than the rates of both g(n). A final takeaway from the lectures was identifying how to represent time efficiency with BigO, in the documents it states that given a t(n) we can identify the Big(O) by eliminating the lower order terms of the function, and eliminate the constant coefficients.

The lectures also provided insights on how to analyze nonrecursive and recursive algorithms. I noted before that recursive algorithms were a bit difficult to understand, so I'll discuss it a bit here. From my understanding it involves analyzing the algorithm for the recursive relation, which is the run time of the algorithm in small input sizes, and determining the initial condition or base conditions that stop the recursion. I think I am slowly understanding how to find the initial condition but identifying the recursive relation was a bit difficult. After finding the two, we can solve by using backwards substitution to determine the time complexity of the algorithm. The backwards substitution wasn't hard to figure out, it was more so finding the general recursive relation.

Lastly we went over briefly the algorithm design known as Brute Force Algorithm and identified the different ways these can be applied especially with selection sorting and sequential searching. It was noted in the lecture that it's one of the easiest to apply and generally acceptable to many problems as it can be mostly refined later if possible. To generally summarize the week, I thought it was quite informative. It made me think much deeper about how algorithms function by figuring out the general t(n) through identifying the basic operations, and it made me apply some form of mathematical practice with the analysis of recursive algorithms. The puzzles were fun to interact with; I did spend a lot of time thinking about the race car puzzle. I personally thought that one was fun, along with the clock hands. Overall this week was quite busy but enjoyable. Here's to another week of Design and Analysis of Algorithms!