⏱️

Big O Notation

44 cards · 🇺🇸 English

Time and space complexity analysis for common algorithms and operations.

Study all 44 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Big O notation

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Big O notation
    A mathematical notation that describes the limiting behavior of a function when the argument tends toward infinity, used to classify algorithms by how their run time or space requirements grow as input size grows
  2. 2Letter 'O'
    Ordnung (German for 'order'), meaning the order of approximation
  3. 3F(n) = O(g(n))
    The function f is bounded above by g (up to a constant factor) asymptotically
  4. 4O(1) complexity
    Constant time - the algorithm takes the same amount of time regardless of input size
  5. 5O(log n) complexity
    Logarithmic time - typical for algorithms that divide the problem in half each step (e.g., binary search)
  6. 6O(n) complexity
    Linear time - the algorithm's runtime grows linearly with input size
  7. 7O(n log n) complexity
    Linearithmic or quasilinear time - typical for efficient comparison-based sorting algorithms like merge sort and heapsort
  8. 8O(2ⁿ) complexity
    Exponential time - the runtime doubles with each additional input element
  9. 9Little-o notation
    A notation where f(n) = o(g(n)) means f grows much slower than g asymptotically
  10. 10Big Omega (Ω) notation
    A notation that provides a lower bound on the growth rate of a function (f is bounded below by g)
  11. 11Big Theta (Θ) notation
    A notation meaning f is bounded by g both above and below (tight bound) - f and g have the same order of growth
  12. 12F(n) ~ g(n)
    Asymptotic equivalence - f is equal to g asymptotically (the ratio f/g approaches 1)
  13. 13Complexity of finding an item in a sorted array with binary search
    O(log n)
  14. 14Complexity of finding an item in an unsorted list with linear search
    O(n)
  15. 15Best possible time complexity for comparison-based sorting
    O(n log n) in the average case
  16. 16Time complexity of quicksort in the average case
    O(n log n)
  17. 17Worst-case time complexity of quicksort
    O(n²)
  18. 18Time complexity of merge sort
    O(n log n) for all cases (best, average, and worst)
  19. 19Time complexity of bubble sort
    O(n²) in the worst and average cases, O(n) in the best case (already sorted)
  20. 20Time complexity of insertion sort
    O(n²) in the worst and average cases, O(n) in the best case
  21. 21Space complexity of an algorithm
    The amount of additional memory space required by the algorithm as a function of input size
  22. 22'in-place'
    An algorithm that requires only O(1) or O(log n) additional space beyond the input
  23. 23Amortized time complexity
    The average time per operation over a worst-case sequence of operations
  24. 24Inverse Ackermann function's complexity
    O(α(n)), which grows extremely slowly - effectively constant for practical purposes (used in disjoint-set operations)
  25. 25Polylogarithmic time
    O((log n)^k) for some constant k - slower than logarithmic but faster than any polynomial
  26. 26Superpolynomial function
    A function that grows faster than n^c for any constant c
  27. 27Subexponential function
    A function that grows more slowly than c^n for any constant c > 1
  28. 28Can you ignore constant factors in Big O notation?
    Yes, constants are omitted: O(5n) = O(n), O(3n²) = O(n²)
  29. 29Can you drop lower-order terms in Big O notation?
    Yes: O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)
  30. 30Is Big O notation an equality or an inequality?
    It's actually an inequality (upper bound) despite using the = symbol, representing 'is element of' a set

And 14 more cards. Study the whole deck free

Articles about this deck

More Programming decks

See all
Study all 44 cards free