# 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)