Algorithms and Complexity: Big O, Omega, and Theta Notations

Flashcards based on the lecture notes about Big O, Big Omega, and Big Theta notations.

What is the formal definition of Big O notation?

T(n) is O(f(n)) if there are positive constants M and n₀ such that T(n) ≤ M×f(n) for all n ≥ n₀

What is the formal definition of Big Omega (Ω) notation?

T(n) is Ω(f(n)) if there are positive constants M and n₀ such that T(n) ≥ M×f(n) for all n ≥ n₀; meaning T(n)'s growth is bounded from below by f(n).

What is the formal definition of Big Theta (Θ) notation?

T(n) is Θ(f(n)) if there are positive constants M1, M2 and n₀ such that M1×f(n) ≤ T(n) ≤ M2×f(n) for all n ≥ n₀; meaning T(n)'s growth is bounded from above and below by f(n).

If T(n) = 3n + 4, show that T(n) is Θ(n).

Prove that T(n) ∈ O(n) AND T(n) ∈ Ω(n). T(n) ≤ 7n for M=7 and n₀=1, thus T(n) ∈ O(n). T(n) ≥ 2n for M=2 and n₀=0, thus T(n) ∈ Ω(n). Since T(n) ∈ O(n) AND T(n) ∈ Ω(n), T(n) ∈ Θ(n).

What is the Big O notation for T(n) = 1*n + 0?

O(N)

What is the Big O notation for T(n) = 2n^2 + 1n + 0?

O(n^2)

What is the Big O notation for T(n) = 2N + 1log(N) + 0?

O(N)

What is the Big O notation for T(n) = 2N + 12^N + 0?

O(2^N)

In the context of linear search, what is the Big O, Big Omega, and Big Theta notation for the best case?

O(1), Ω(1), Θ(1)

In the context of linear search, what is the Big O, Big Omega, and Big Theta notation for the worst case?

O(N), Ω(N), Θ(N)

In the context of linear search, what is the Big O, Big Omega, and Big Theta notation for the average case?

O(N), Ω(N), Θ(N)

True or False: Linear search is O(n)

True: There is no input of size n for which the runtime is not bounded from above by n.

True or False: Linear search is Ω(1)

True: There is no input of size n that takes less than a constant amount of time.

True or False: Linear search is Θ(n)

False: There is an input of size n, the best case, specifically, for which the runtime is Θ(1).

Which of the following statements is false given a time complexity T(n) = 0.01n^2 + 4log(n) + 3?
T(n) ∈ Θ(n^2)
T(n) ∈ Ω(log n)
T(n) ∈ O(log n)
T(n) ∈ O(n!)

T(n) ∈ O(log n) is the correct answer. because big-O defines an upper bound, so T(n) is only big-O of functions that grow as fast (or faster) than the dominant term n^2

Consider the code fragment below. Assume the inputs are two arrays of size N and M respectively. Determine the time complexity in the big- θ notation.
for (i = 0; i < N; i++) {
Sequence of statements with θ(N) complexity
}
for (j = 0 ; j < M; j++) {
Sequence of statements with θ(1) complexity
}
i) θ(max(N,M))
ii) θ(max(N^2,M))
iii) θ(N^2M)
iv) θ(NM+N)

θ(max(N^2,M)). Loop 1 has complexity θ(N^2), and Loop 2 has complexity θ(M). Overall complexity is the max of the two loops.

What does Big O notation represent?

The upper bound of an algorithm's growth rate.

What does Big Omega (Ω) notation represent?

The lower bound of an algorithm's growth rate.

What does Big Theta (Θ) notation represent?

A tight bound, meaning the rate of growth is equal to a specified value.