ScaleFree

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
  1.  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
  1. //Part 1
  2. sum = 0;    -------------------- Statement 1

  3. //Part 2
  4. for (int i = 0; i <= n; i++)
  5. 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
  1. value = 0;
  2. for (i = 1; i <= n; i++)
  3.     for (j = 1; j <= n; j++)
  4.     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
  1. value = 0;
  2. if(value > 0)
  3. {
  4.   for (i = 1; i <= n; i++)
  5.     for (j = 1; j <= n; j++)
  6.       for (k = 1; k <= n; k++)
  7.       value = 2;              ---------------- Statement 1
  8. }
  9. else
  10. {
  11.   value++;                    ---------------- Statement 2
  12. }

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.
  • 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
What is the Big-O if T(n) = C + Cn/2 + Cn² = Cnlog(n)?
 O(n)
 O(n²)
 O(n³)
 None of the Above


Quiz 2
  1. for (i = 1; i <= n; i++)
  2.     for (j = 1; j <= n; j++)
  3.          sum ++;
  4.     for (k = 1; k < n; k++)
  5.          A[k] = k;

What are the Big-O, Big Omega, and Big Theta of the program?
 O(n), Ω(n²), θ(n²)
 O(n²), Ω(n²), θ(n)
 O(n²), Ω(n²), θ(n²)
 None of the Above


Quiz 3
  1. sum1 = 0;
  2. for (i = 1; i <= n; i++)
  3.     for (j = 1; j <= n; j++)
  4.          sum1 ++;
  5. sum2 = 0;
  6. for (i = 1; i <= n; i++)
  7.     for (j = 1; j <= n; j++)
  8.          sum2 ++;

What are the Big-O, Big Omega, and Big Theta of the program?
 O(n²), Ω(n²), θ(n²)
 O(n²), Ω(n²), θ(n)
 O(n³), Ω(n²), θ(n²)
 O(n³), Ω(n²), θ(n³)

( If you like the content here, follow TSP on social media to get notified on future updates)




Comments

Share on Social Media

Most Viewed Posts

DS & A (Lists - Array Based)

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS