# Unit 12 - Algorithms Flashcards

define big O notation

an approximation of how well an algorithm scales with an increasing data set

two main parts of big o

- time complexity
- memory complexity

description of O(1)

constant

description of O(log n)

logarithmic

description of O(n)

linear

description of O(n log n)

linearithmic

description of O(n^2)

polynomial

description of O(2^n)

exponential

description of O(n!)

factorial

best to worst big O scenarios

O(1)

O(log n)

O(n)

O(n log n)

O(n^2)

O(2^n)

O(n!)

best, average and worse case scenarios of time complexity for linear search

best - O(1)

average - O(n)

worst - O(n)

best, average and worse case scenarios of time complexity for binary search array

best - O(1)

average - O(log n)

worst - O(log n)

best, average and worse case scenarios of time complexity for binary search tree

best - O(1)

average - O(log n)

worst - O(n)

best, average and worse case scenarios of time complexity for hashing

best - O(1)

average - O(1)

worst - O(n)

best, average and worse case scenarios of time complexity for breadth/depth-first traversal of a graph

best - O(1)

average - O(V + E)

worst - O(v^2)

V = vertices

E = edges

best, average and worse case scenarios of time complexity for bubble sort

best - O(n)

average - O(n^2)

worst - O(n^2)

best, average and worse case scenarios of time complexity for insertion sort

best - O(n)

average - O(n^2)

worst - O(n^2)

best, average and worse case scenarios of time complexity for merge sort

best - O(n log n)

average - O(n log n)

worst - O(n log n)

best, average and worse case scenarios of time complexity for quick sort

best - O(n log n)

average - O(n log n)

worst O(n^2)

space complexity for bubble sort

O(1)

space complexity for insertion sort

O(1)

space complexity for merge sort

O(n)