Big O Notation Flashcards
What is Big O Notation?
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
What is O(1)?
O(1), or constant time, describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
Examples: determining if a binary number is even or odd; calculating (-1)^n; using a constant-size lookup table
What is O(log n)?
O(log n), or log time, describes an algorithm that will halve the number of items for each iteration of execution.
Examples: binary search, binomial heap
What is O(n)?
O(n), or linear time, describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
Examples: finding a number in an unsorted array (worst case, the number will be at the end)
What is O(n*log n)?
O(n*log n), or linearithmic or loglinear time, describes an algorithm that will pass through the input once and deliver results in an log n fashion.
Examples: heapsort, quicksort (best and average case), and mergesort
What is O(n^2)?
O(n^2), or quadratic time, describes an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.
Examples: quicksort(worst case), insertion sort, selection sort
What is O(c^n)?
O(c^n), or exponential time, describes an algorithm whose growth will be multiplied by c with each additional element in the input data set.
Examples: finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
What is O(n!)?
O(n!), for factorial time, describes an algorithm whose growth by multiplying every member of the input set with every other member.
Examples: solving the traveling salesman problem via brute-force search
What is O(n^1/2)?
Fractional time.
Examples: searching a kd-tree
