What is Big O?

O(n)

one loops runs n times

O(log n)

Doubles each iteration

O(n²)

two nested loops

O(n)

two separate loops: n + n = 2n → O(n)

O(log n)

triples each iteration

O(n log n)

outer loop is n, inner loop is log n

O(n²)

total work is 1 + 2 +.. + n = n² / 2

O(log n)

divides by 2 each iteration

O(n³)

three nested loops

O(n)

one recursive call per function call

O(2^n)

two recursive calls per function call

O(1)

always run 100 times (constant)

O(n)

O(log n) + O(n) = O(n)

O(n² log n)

two nested linear loops and one logarithmic loop

O(n)

worst case checks every possible divisor

O(n log n)

log n outer iterations x n inner iterations

O(n)

O(n) + O(log n) = O(n)

O(n)

one recursive call each time

O(n³)

O(n³) + O(log n) = O(n³)

O(n log n)

log n iterations of a loop that does n work each time

O(n)

the loop executes n times

O(log n)

the value is multiplied by 5 each iteration

O(n)

the inner loop runs a constant 50 times

O(n)

the total work is O(n) + O(log n), and O(n) is larger

O(n log n)

the outer loop runs log n times and the inner loop runs n times

O(n²)

the innermost loop is constant (100 iterations), so the work is n x n x 100 = O(n²)

O(n)

the value increases by a constant amount each iteration

O(n log n)

the outer loop is n and the inner loop is log3(n)

O(n²)

the total work is 1 + 2 + … + n which is about n² / 2

O(n)

each recursive call makes exactly one more recursive call

O(2^n)

every recursive call creates two more recursive calls

O(1)

the loop always run 100 times, regardless of n

O(n)

the work is O(log n) + O(n), which simplifies to O(n)

O(n² log n)

the loop runs n x n x log n times

O(n)

in the worst case, the loop checks every value down to 1

checks each element one at a time from beginning until it finds the target value or reaches the end of the list

linear search O(n)

has to be sorted, then repeatedly checks the middle element of a sorted list and eliminates half of the remaining elements until the target is found or no element remains

binary O(log n)

repeatedly finds the smallest element in the unsorted portion of the list and swaps it with the first unsorted position

selection sort O(n²)

fibonacci sequence

O(2^k)

imporved fibonacci

O(n)