Big O Notation Flashcards
What do O and n stand for in Big O Notation?
O: “order of the functions” “operarations”
n: “the size of the dataset”
What are the common functions for data structures?
access, search
insert, delete
What is the most common space complexity?
O(n)
linear time
What is the space complexity for a Skip List?
O(n log n)
What is constant time?
O(1)
An operation that takes the same amount of time, no matter the size of the dataset
What is linear time?
O(n)
An operation where time increases as size increases
What is logarithmic time?
O(log n)
An operation that decreases the size of the dataset each iteration
What is quadratic|polynomial time?
O(n^2)
An operation that runs more than one loop (nested loops)
What is exponential time?
O(2^n)
An operation that has multiple permutations for each input
“Brute Force” algorithms
What are the time complexities? Rate them fastest to slowest.
Constant O(1) fastest Logarithmic O(log n) fast for large datasets Linear O(n) fast for small datasets O(n log n) slower than linear Quadratic O(n^2) slower as data grows Exponential O(2^n) very slow Factorial O(n!) Slowest
What are the time complexities of access & search for stacks, queues, and linked-lists?
Both are linear time O(n)
What are the time complexities of insert & delete for stacks and queues?
Both are constant time O(1)
What are the time complexities of an array?
Access O(1) constant time
Search O(n) linear time Insertion O(n) Deletion O(n)
What are the time complexities of
access, search, insert, delete for
B-tree, Red-Black-tree, & AVL-tree?
All are logarithmic time O(log n)
What is the time complexity of quicksort?
Space complexity?
Worst: O(n^2) quadratic
Can be O(n log n)
Space: O(log n)
What is the time complexity of mergesort?
Space complexity?
Time O(n log n)
Space O(n) linear
What is the time complexity of timesort?
Space complexity?
Time: O(n log n)
Space: O(n) linear
What is the time complexity of heap sort?
Space complexity?
Time: O(n log n)
Space: O(1)
What are the time and space complexities of bubble, insertion, and selection sort?
Time: O(n^2) quadratic
Space O(1)
What is an “in-place” algorithm?
An algorithm that transforms its input and uses no auxiliary data structure
What is a pointer?
An object that stores a memory address
A pointer references a location in memory
What are the pros and cons of an in-place algorithm
Pro: it is very time efficient
Con: it mutates the original data structure
What are the time complexities for a hash table?
search, insert, delete: Worst O(n) linear Best O(1) constant
What are the time complexities for a skip list, binary search tree, and KD tree?
access, search, insertion, delete:
Worst: O(n)
Best: O(log n)
What are the time complexities of a splay tree?
search, insert, delete: Always O(log n)
What arenthe time complexities of a Cartesian Tree?
search, insert, delete:
Worst: O(n)
Best: O(log n)
What is accessing a data structure?
access:
When you use the element’s index|address to get the value
What is searching a data structure?
Searching is iterating/traversing the data structure to find the element you are looking for
What is insertion?
Adding an element to a data structure
What is deletion?
Removing an element from a data structure
What is Amortized Time?
Essentially amortized time means “average time taken per operation, if you do many operations”.
If you do an operation a million times, you don’t really care about the worst-case or the best-case of that operation.
What you care about is how much time is taken in total when you repeat the operation a million times.
