DS & A (Algorithm Analysis - 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², n 0 = 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², n 0 = 1 3n² = 3n² Ω(f(n)) = Ω(n²) Therefore, T(n) is in Ω(n²)