CST370 Design and Analysis of ALgorthms Week 2

Week 2 of this class was a lot to take in but I was able to follow along well. Algorithm Analysis is the process to identify the category or order of growth of an algorithm. We learn about the three notations which are the upper bound, tight bound and lower bound. We learn about Asymptotic Notations for Algorithm analysis. An algorithm’s running time t(n) is said to be in O(g(n)),
denoted t(n) ∈ O(g(n)), if there exist positive constants c and n0 that satisfy the following condition. As a sample if t(n) = n^2 + 3*n + 5 then we can say that t(n) is O(n^2) since we can ignore the constants and the function has n^2 as the highest power. We also learn about the order of growth of algorithms. First is constant which is O(1) then it goes for more execution time. Logarithmic O(log N), Linear O(N), Log-linear O(N log N), Quadratic O(N^2), Cubic O(N^3), Exponential O(2^N) and lastly Factorial O(N!).

 Another topic that was discussed was the Non-Recursive algorithms which are algorithms that do not contain recursive calls. For this type of algorithms we still use Asymptotic notation for algorithm analysis. The professor gave more samples on how to analyze the order of growth for non-recursive algorithms such as the number of binary digits. We also learn on how to analyze recursive algorithm which are the algorithm that contains recursive calls and as a sample professor use factorial function.We can basically know when to end when the function calls F(0) since there are no more operation. Basically for factorial function we can recognize that the number of multiplications for F(n) is n. We also analyze the samples using recurrence relation and backward substitution.

 Lastly we talked about the topic of algorithm analysis technique called brute force. It is basically a straightforward approach to solving a problem, directly based on the problem statement and definitions  of the concept involved. For example when looking for a number in an array of numbers from 1-100. The solutions is to simply check the numbers starting from 1 and go sequentially until the number we are searching for is found.

As for our homework exercise, I was able to recall some ways to add arrays and how to work with array containing arrays. It was a good review on how to code in C++. For the problem two I was able to also review on how to manipulate times and recall about the library iomanip since it was required for the output of the answer.