CST370 - Week 2

 

CST370-30_2252: Design & Analysis of Algorithms – Week 2

The second week of this course introduces the asymptotic notations that rank the order of growth. The framework analysis for ranking the orders has three notations: big oh (O), big omega (ꭥ), and big theta(Ꝋ). I found the informal definitions of the notations helpful in understanding their differences. For example, the definition of the big O used the function g(n) as the upper bound of all functions with the same order of growth or lower. On the other hand, ꭥ(g(n)) is for all functions with the same order of growth or higher, and Ꝋ(g(n)) is for all functions with the exact same order of growth.

The formal mathematical definition of the three asymptotic notations asserts the informal definitions. If t(n) is in O(g(n)) if t (n) ≤ cg(n) for Ɐ n ≥ no, and Ǝ c is a positive constant and no is a non-negative number. Similarly, if t(n) is in ꭥ(g(n)) if t(n) ≥ cg(n) for Ɐ n ≥ no, and Ǝ c is a positive constant and no is a non-negative number. The t(n) is in Ꝋ(g(n)) if c2g(n) ≤ t (n) ≤ c1g(n) for Ɐ n ≥ no, and Ǝ c1 and c2 are a positive constant and no is a non-negative number.

We have reviewed the analysis of non-recursive algorithms for simple n × n matrices multiplication with three nested loops. The order of growth was calculated by the triple sum of unchanged variable loops, yielding growth order. The second example highlighted the loop’s variable changes for an algorithm that finds the number of binary representations in a positive number. The halved value of the n in each iteration returns a growth order of.

For the analysis of the recursive algorithm, we evaluated the example of the first n cubes and the tower of Hanoi puzzle using backward substitution. The method uses an initial condition and a general form of the basic operation to reach a result by induction.

The module ends with an introduction to the brute-force method. The approach of this strategy is to solve the problem directly. The textbook illustrates the solution for an exponential calculation of a raised to the power of n, representing the solution as the multiplication of a repeated n times. While the brute-force approach can be inefficient, it is widely used in solving important problems like sorting and searching. The two applications provided were bubble sort and selection sort. Using a brute-force strategy could lead to improvements after the first version of the algorithm. However, a bubble sort, for instance, will remain big theta(n²) in its time complexity. That concludes this module, and I look forward to the next one.