CST-370 Week 2

 This week, I learned to mathematically analyze algorithms using Asymptotic notations on algorithms such as non-recursive and recursive.

Asymptotic Notations

Algorithm analysis is to identify the time category of an algorithm (time complexity). The most common categories are: 1, log n, n, nlogn, n^2, n^3, 2^n, n!

Three notations that represent an algorithm's efficiency: O(f(n)) <- upper bound, Θ (f(n)) <- tight bound, and Ω(f(n)) <- lower bound.

f(n) written as O(n^2), Θ (n), Ω(nlogn)

Upper bound: All functions with lower or same order of growth as f(n). Ex: f(n) = O(n^2) Functions that satisfy: 1, n, nlogn, n^2, 5n, 7n^2, 500. 

Tight bound: All functions with the same order of growth as f(n). Ex: f(n) = Θ (n). Functions that satisfy: 4n, 20n

Lower bound: All functions with same or higher order of growth as f(n). Ex: f(n) = Ω(n*logn). Functions that satisfy: n*logn, n, n^2, n^3, 4n^3 

Two Rules to Simplify T(n)

T(n) => O(n)

1. 1. Eliminate lower order terms. Ex: T(n) = 4*n + 5 => 4*n
2. 2. Eliminate constant coefficients. T(n) = 4*n => n => O(n)

Ex: T(n) = 0.5*n*logn + (2*n + 7) <- 2*n +7 is lower order, so remove

=> 0.5*n*logn <- remove coefficient

=>n*logn

=> O(n*logn)

Non-recursive Algorithms

• 1. Algorithms that do not contain recursive calls
• 2. Use of Asymptotic notations for time efficiency analysis

Analysis of Recursive Algorithms

Algorithms are recursive if it contains recursive calls.

 Example: 

factorial function n!: n! = n*(n-1)!, 0! = 1

Algorithm F(n)

1. if (n = 0)

3.     return 1

4. else

5. return F(n-1) * n

How to determine time complexity of above algorithm?

For input n, the calls are f(n), f(n-1), f(n-2), ..., 2, 1, 0 => n + 1 => O(n)

Example 2.

1 Algorithm S(n)

2. if n = 1

3.     return 1

4. else 

5.    return S(n-1) + (n * n * n)

Steps for analysis:

1. Basic operation (multiplication operation)

2. Recurrence relation (M(n) = M(n-1) + 2)

3. Initial condition (M(1) = 0)

Backward Substitution method:

M(n) = M(n-1) + 2

= [M(n-2) + 2] + 2 // Replace "M(n-1)" with "M(n-2) + 2"

= M(n-2) + 2 + 2

= [M(n-3) + 2] + 2 + 2 // Replace "M(n-2)" with "M(n-3) + 2"

= M(n-3) + 2 + 2 + 2

...

= M(n-i) + 2*i // For a general number i, we will get this

... // Solve for base case (n-i = 1 => i = n + 1)

= M(1) + 2*(n-1) // Note that the initial condition is M(1) = 0

= 0 + 2*(n-1)

= 2*(n-1) => O(n)

Brute force

Brute force: A straightforward approach to solving a problem, usually based on the problem statement and definitions of the concepts involved.