Big O Notation - Time Complexity
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/63
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai | Chat |
|---|
No analytics yet
Send a link to your students to track their progress
64 Terms
What is the Big O of this?
O(n)
What is the Big O of this?
O(n²)
What is the Big O of this?
O(log n)
Which is asymptotically faster: O(n) or O(log n)?
O(log n)
What is the best possible Big O complexity?
O(1)
What is generally the fastest practical complexity for searching sorted data?
O(log n)
Which grows faster: O(n) or O(n log n)?
O(n log n)
Which grows faster: O(n²) or O(2ⁿ)?
O(2ⁿ)
Which grows the fastest?
O(n²)
O(2ⁿ)
O(n!)
O(n)
O(n!)
What happens to O(1) as n increases?
It stays constant
Why do programmers care about Big O?
It predicts how algorithms scale with larger inputs
Does Big O ignore constants?
Yes: O(2n) → O(n)
Does Big O ignore lower-order terms?
Yes: O(n² + n) → O(n²)
Which dominates?
n²
Which dominates?
n log n
Is O(n + m) always simplified?
No. It stays O(n + m) if n and m are independent.
Is O(n + n) simplified?
Yes → O(n)
Which is usually preferred?
O(n²)
O(n log n)
O(n log n)
What is the Big O?
O(nm)
What is the Big O?
O(n log x)
What is the Big O?
O(n)
What is the Big O of finding an element in an unsorted array?
O(n)
What is the Big O of binary search?
O(log n)
What kind of algorithm usually has O(n log n)?
Efficient comparison-based sorting algorithms
Array access
O(1)
Search in an unsorted array
O(n)
Insert at the end of a dynamic array (average)
O(1)
Insert at the beginning of an array
O(n)
Delete from the beginning of an array
O(n)
Why is inserting at the beginning O(n)
Every element must shift 1 position
Access the 50th node of a linked list
O(n)
Insert at the head of linked list
O(1)
Delete the head in linked list
O(1)
Search a linked list?
O(n)
Average lookup in hashmap
O(1)
Average insertion/deletion in hashmap
O(1)
Worst-case lookup in a hash table
O(n)
Search/insert/delete in a balanced BST
O(log n)
Search in an unbalanced BST
O(n)
Push/pop/peek stack
O(1)
Enqueue/dequeue/peek front in queue
O(1)
Which data structure provides average O(1) lookup
hashmap
Which data structure allows O(1) push and pop
stack
Which search algorithm requires sorted data?
bst
Which is faster for searching large sorted data?
Linear Search
Binary Search
binary search
Which complexity is considered efficient for sorting?
O(n log n)
Which complexity should generally be avoided for large inputs?
O(2ⁿ) and O(n!)
Why is dividing n by 2 O(log n)?
Because the number of times you can halve n until reaching 1 is log₂(n)
What pattern usually means O(log n)?
Repeatedly cutting the problem in half