### DS & A (Algorithm Analysis - Examples)

###
__ |Examples - CHAPTER 8|__

In our previous chapter, we discussed the different measures of Algorithm Complexity, namely Big-O, Big Omega and Big Theta. This chapter will be following after the concepts from the previous chapter(Measures of Algorithm Complexity). So, having basic knowledge about the different measures of Algorithm Complexity is a must for someone reading this chapter.

**Pre-requisite:**

Proper understanding of Running Time, Big-O, Big Omega, and Big Theta(If those terms are new to you, you can learn more about them here)

**Big-O, Big**

**Ω, and Big**

**θ if Running time is known...**

**Example 1**

**Running Time, T(n) = 3n²**

**Big O**

T(n) ≤ cf(n) {By definition of Big O}

3n² ≤ cf(n)

By substituting,

c = 3, f(n) = n², n0 = 1

3n² = 3n²

O(f(n)) = O(n²)

Therefore, T(n) is in O(n²)

**Big Ω**

T(n) ≥ cf(n) {By definition of Big Ω}

3n² ≥ cf(n)

By substituting,

c = 3, f(n) = n², n0 = 1

3n² = 3n²

Ω(f(n)) = Ω(n²)

Therefore, T(n) is in Ω(n²)

**Big**

**θ**

Since T(n) is in O(n²) & T(n) is in Ω(n²)

Therefore, T(n) is in θ(n²)

**Example 2**

**Running Time, T(n) = 3n² + n**

**Big O**

T(n) ≤ cf(n) {By definition of Big O}

3n² + n ≤ 3n² + n² ⇒ 3n² + n ≤ 4n²

By substituting,

c = 4, f(n) = n², n0 = 1

3n² + n ≤ 4n²

O(f(n)) = O(n²)

Therefore, T(n) is in O(n²)

**Big Ω**

T(n) ≥ cf(n) {By definition of Big Ω}

3n² + n ≥ 3n² + n² ⇒ 3n² + n ≤ 4n²

By substituting,

c = 4, f(n) = n², n0 = 1

3n² + n ≥ 4n²

Ω(f(n)) = Ω(n²)

Therefore, T(n) is in Ω(n²)

**Big**

**θ**

Since T(n) is in O(n²) & T(n) is in Ω(n²)

Therefore, T(n) is in θ(n²)

**Big-O, Big**

**Ω, and Big**

**θ of a program...**

**Example 3**

- a = b;

- Usually, time Complexity of an Assignment, Addition, and Subtraction operation are constant. So it is denoted by C. Therefore, Running Time, T(n) = C
- Therefore, T(n) is in O(1), Ω(1) & θ(1)

**Example 4**

- //Part 1
- sum = 0; -------------------- Statement 1
- //Part 2
- for (int i = 0; i <= n; i++)
- sum += n; -------------------- Statement 2

- Running Time, T(n) = Running Time of Part 1 + Running Time of Part 2
- Running Time of Part 1 = Running Time of Statement 1 = C
- Since "Part 2" has a for loop which executes n times. So, Statement 2 will be executed n times.
- Running Time of Part 2 = (n * Running Time of Statement 2) = (n * C) = Cn
- Running Time, T(n) = (C + Cn)
- Therefore, the algorithm is in O(n), Ω(n) & θ(n)

**Example 5**

- value = 0;
- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- value = 2; ---------------- Statement 1

- Running Time, T(n) = n * n * T(Statement 1)
- Running Time, T(n) = n * n * C
- Running Time, T(n) = n² * C
- Running Time, T(n) = Cn²
- Therefore, the algorithm is in O(n²), Ω(n²) & θ(n²)

**Example 6**

- value = 0;
- if(value > 0)
- {
- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- for (k = 1; k <= n; k++)
- value = 2; ---------------- Statement 1
- }
- else
- {
- value++; ---------------- Statement 2
- }

**Note :**

1) In case the program contains an "if-else" statement, consider the greater complexity of the then/else clause.

2) In case the program contains a "switch" statement, consider the most expensive case.

2) In case the program contains a "switch" statement, consider the most expensive case.

- Since, if(value > 0){...} > else{...}
- Therefore, Running Time, T(n) = n * n * n * T(Statement 1)
- Running Time, T(n) = n * n * n * C
- Running Time, T(n) = n³ * C
- Running Time, T(n) = Cn³
- Therefore, the algorithm is in O(n³), Ω(n³) & θ(n³)

**Quiz 1**

**Quiz 2**

- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- sum ++;
- for (k = 1; k < n; k++)
- A[k] = k;

What are the Big-O, Big Omega, and Big Theta of the program?

**Quiz 3**

- sum1 = 0;
- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- sum1 ++;
- sum2 = 0;
- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- sum2 ++;

What are the Big-O, Big Omega, and Big Theta of the program?

*( If you like the content here, follow*

**TSP**on social media to get notified on future updates)

## Comments

## Post a Comment