Big-O Notation Flashcards

Flashcards covering the concepts of Big-O notation, time complexity analysis, and algorithm examples from the lecture notes.

What is the Big O notation used for in practice?

Calculating the complexity of example algorithms.

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

O(N)

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

O(N^2)

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

O(N^3)

What is the Big O notation for a constant time T(N) = Constant?

O(1)

What is the Big O notation for a linear time T(N) = C1 x N + C2?

O(N)

What is the Big O notation for a logarithmic time T(N) = C1 x log2 N + C2?

O(log N)

What is the Big O notation for a quadratic time T(N) = C1 x N^2 + C2 x N + C3?

O(N^2)

What is the Big O notation for the best case of a linear search?

O(1)

What is the Big O notation for the worst case of a linear search?

O(N)

What is the Big O notation for the average case of a linear search?

O(N)

What is the worst case time complexity of a loop that runs a constant number of times with O(1) expressions inside?

O(1)

Given T1(n) is O(N) and T2(n) is O(M), what is the combined time complexity for sequential loops?

O(max(N, M))

If N is much greater than M, and T1(n) is O(N) and T2(n) is O(M), what is O(max(N, M))?

O(N)

What is the overall time complexity of two nested loops each running N times, with O(1) operations inside?

O(N^2)

What is the time complexity of nested loops where the number of iterations depend on each other?

Careful counting of operations or using Sigma notation

A

A

A

A

A

A

When determining the Big O notation of sequential loops, what should you identify?

Find the dominant term (i.e., the loop that takes the longest)

What is the time complexity of nested loops equal to?

The number of times innermost statement is executed*complexity of statement