big o notation Flashcards
learn big o (27 cards)
What does Big O notation describe?
The performance or complexity of an algorithm in terms of time and space.
True or False: Big O notation can provide an exact number of steps an algorithm takes.
False
Fill in the blank: The notation O(n) represents ______.
Linear time complexity.
What is the Big O notation for constant time complexity?
O(1)
Which of the following is an example of logarithmic time complexity?
O(log n)
What is the time complexity of a binary search algorithm?
O(log n)
True or False: O(n^2) indicates quadratic time complexity.
True
What does O(n!) represent?
Factorial time complexity.
Which Big O notation indicates the worst-case scenario for an algorithm?
Big O notation itself represents the worst-case scenario.
What is the time complexity of a simple loop that iterates n times?
O(n)
Fill in the blank: The term ______ describes the space complexity of an algorithm.
Big O notation.
What is the significance of the constant factors in Big O notation?
They are ignored as they do not affect the growth rate.
True or False: Big O notation can be used for both time and space complexity.
True
What is the time complexity of a merge sort algorithm?
O(n log n)
Which of the following has the highest growth rate: O(n), O(n log n), O(n^2), O(2^n)?
O(2^n)
What is the time complexity of accessing an element in an array?
O(1)
Fill in the blank: An algorithm that reduces the problem size by half each iteration has a complexity of ______.
O(log n)
What is the time complexity of bubble sort in the worst case?
O(n^2)
True or False: The notation O(n^3) represents cubic time complexity.
True
What is the Big O notation for an algorithm that runs in linear time?
O(n)
Which algorithm has a time complexity of O(n log n) in the average case?
Quick sort
What is the space complexity of an algorithm that uses a fixed amount of space regardless of input size?
O(1)
Fill in the blank: The notation O(n^2) is often associated with ______ algorithms.
Quadratic
