Time Complexity

Asymptotic Notations

1. Big oh - $O$ - Upper bound - $f(n) = O(g(n))$ iff $f(n) \le c \cdot g(n)$ - Any higher/equal order function than average case

2. Big omega - $\Omega$ - Lower bound - $f(n) = \Omega(g(n))$ iff $f(n) \ge c \cdot g(n)$ - Any lower/equal order function than average case

3. Theta - $\theta$ - Average bound - $f(n) = \theta(g(n))$ iff $c_1 \cdot g(n)\le f(n) \le c_2 \cdot g(n)$

Since $\theta$ gives most accurate bound of a function, it is preferred over $O$ and $\Omega$ which are boundless.

Note: These aren't linked with best case or worst case scenarios, these are just notations. Worst case and best case can be shown using any of these notations.

Big Oh

Theta

Big Omega

Properties

Property	O	Ω	θ
Reflexive
Transitive
Symmetric
Transpose Symmetric

Transpose Symmetric is if $f(n) = O(g(n))$ then $g(n) = \Omega(f(n))$

Comparing Functions

• Functions can be directly compared, however, two functions can be of same complexity (asymptotically equal) even if their constants are unequal. Natively constants do not hold significance in comparing functions.

• If two functions cannot be directly compared (i.e. powers exist), logarithms can be used to compare such functions, however, when taking logarithm - any constants generated by application of logarithm DO HOLD significance and hence after application of logarithm, two functions cannot be asymptotically equal if they have differing constant coefficients.

Examples

1. Functions $2n^{\sqrt n}$ and $3n^{\sqrt n}$ are asymptotically equal.

2. Functions $2^{2n^{\sqrt n}}$ and $2^{3n^{\sqrt n}}$ are NOT asymptotically equal, even though on application of logarithm it produces the same functions as in Example 1.

Big O Cheat Sheet

bigocheatsheet.com

Calculating complexity

1 sec = $10^8$ operations (approx.)

Example

Time constraint: 20 seconds

$0 < n \le 2 \times 10^5$

Here to find out the time complexity, consider $n^2 = 4 \times 10^{10}$ which would equal to 400 seconds. Hence, time complexity here should be less than $O(n^2)$.