AsymptoticNotation.md (1593B)
1 # Asymptotic Notation 2 3 L1 MIT 4 5 **Definition:** Asymptotic notation describes the running time of an algorithm. 6 7 #### Types of complexity notation 8 9 There are three different notations for this big O, beg Theta, and big Omega. 10 11 1. Big Theta 12 - Big Theta notation creates a tight bound about asymptotic behavior. This is a precise growth rate bound between O(f(n)) and Omega(f(n)). 13 14 2. Big Omega 15 - Big Omega notation is used to describe the lower bound (best case) complexity. This value describes a functions complexity as at least whatever is specified. As such a function with n^3 growth can be stated as Omega(n^c) where n <= 3. Subsequently, it is also true that Omega(n^1) can describe this function. 16 17 3. Big O 18 - Big O notation is used to describe the upper bound (worst case) complexity. An interesting note is that the function with growth 7n^3 + 2n^2 can have O(n^3) time complexity, but more accurately we could say O(n^c) where c >= 3. This is because we are stating it does not grow faster than n^c. Such is the case then that O(n^10) is also true as the complexity does not grow faster than that. 19 20 Note: When describing loose bounds (2n = o(n^2)) we use lowercase letters such as little o. This implies that we are describing an upper bound that is guaranteed to be larger than the growth rate that is not tight to the upper bound of the algorithm like how big O would be. 21 22 #### Common complexities 23 24 O(1) - Constant 25 26 O(logn) - Logarithmic 27 28 O(n) - Linear 29 30 O(nlogn) - Log Linear 31 32 O(n^2) - Quadratic time 33 34 O(n^c) - Polymnomial time (arbitrary constant c) 35 36 2^O(n) - Exponential Time