Explore tens of thousands of sets crafted by our community.
Algorithm Complexity and Big O Notation
7
Flashcards
0/7
Constant Time
Big O Notation: O(1) Examples: Accessing a specific array element by index, determining if a number is even or odd.
Linear Time
Big O Notation: O(n) Examples: Summing all elements in an array, linear search on an unsorted array.
Cubic Time
Big O Notation: O(n^3) Examples: Naive matrix multiplication, solving the Rubik's Cube using a straightforward algorithm.
Linearithmic Time
Big O Notation: O(n log n) Examples: Quick sort, merge sort, heap sort for sorting arrays.
Logarithmic Time
Big O Notation: O(log n) Examples: Binary search on a sorted array, finding the largest power of two less than or equal to a given number.
Quadratic Time
Big O Notation: O(n^2) Examples: Bubble sort, insertion sort, and selection sort for small arrays, checking for duplicates in an array by comparing each pair of elements.
Exponential Time
Big O Notation: O(2^n) Examples: Brute-force solutions for the traveling salesman problem, recursive algorithms that generate all subsets of a set (the power set).
© Hypatia.Tech. 2024 All rights reserved.
