C949- Study Guide v3 (Python Version)
Is a way to describe the performance and efficiency
Big O Notation of an algorithm. It tells us how the running time
and space requirements of an algorithm scale with
the scale input size.
Refers to the amount of time an algorithm takes to run
time complexity as a function of the input size. It provides an
estimation of the number of operations or instructions
executed by the algorithm. We express it using Big O
Notation.
Refers to the amount of memory or space it requires
to run as a function of the input size. It estimates the
space complexity
additional space needed to store variables, data
structures, and other resources used by the
algorithm. Space complexity is also expressed in Big
O Notation.
The algorithm takes a constant amount of time
O(1) Constant time
complexity regardless of the input size. Accessing an element in
an array by index.
The algorithm's running time grows linearly with the
O(n) Linear time complexity
input size. Example: Traversing an array and linked list.
The algorithm's running time grows quadratically with
O(n^2) Quadratic time
complexity the input size. Example: Nested loops iterating over
an array.
The algorithm's running time grows logarithmically
O(log n) Logarithmic time
complexity with the input size. Example: Binary search in a
sorted array.
The algorithm's space usage grows in proportion to n
O(n log n) Linearithmic time
multiplied by the logarithm of
complexity
n. Example: Efficient sorting algorithms like merge sort and
quicksort.
The algorithm's running time grows exponentially with
O(2^n) Exponential time
, the input size. Example: Exhaustive search algorithm.
complexity
Is a way to describe the performance and efficiency
Big O Notation of an algorithm. It tells us how the running time
and space requirements of an algorithm scale with
the scale input size.
Refers to the amount of time an algorithm takes to run
time complexity as a function of the input size. It provides an
estimation of the number of operations or instructions
executed by the algorithm. We express it using Big O
Notation.
Refers to the amount of memory or space it requires
to run as a function of the input size. It estimates the
space complexity
additional space needed to store variables, data
structures, and other resources used by the
algorithm. Space complexity is also expressed in Big
O Notation.
The algorithm takes a constant amount of time
O(1) Constant time
complexity regardless of the input size. Accessing an element in
an array by index.
The algorithm's running time grows linearly with the
O(n) Linear time complexity
input size. Example: Traversing an array and linked list.
The algorithm's running time grows quadratically with
O(n^2) Quadratic time
complexity the input size. Example: Nested loops iterating over
an array.
The algorithm's running time grows logarithmically
O(log n) Logarithmic time
complexity with the input size. Example: Binary search in a
sorted array.
The algorithm's space usage grows in proportion to n
O(n log n) Linearithmic time
multiplied by the logarithm of
complexity
n. Example: Efficient sorting algorithms like merge sort and
quicksort.
The algorithm's running time grows exponentially with
O(2^n) Exponential time
, the input size. Example: Exhaustive search algorithm.
complexity
