WEEK 3: COMPLEXITY Flashcards
(15 cards)
refers to the measure of the computational resources used by an algorithm to solve a problem. these resources typically include time and space, and the goal is to minimize their usage to achieve optimal performance
algorithm efficiency
this measures the amount of time an algorithm takes to complete as a function of the size of the input
time complexity
time complexity is often expressed using this
big-O notation
this describes the upper bound of the algorithm’s running time
big-O notation
constant time, where running time does not depend on the input size
O(1)
logarithmic time, where the running time grows logarithmically with the input size
O(logn)
linear time, where the running time grows liearly with the output
O(n)
linearithmic time, common in efficient sorting algorithms like mergesort and heapsort
O(n logn)
quadratic time, where the runnng time grows quadratically with the input size, common in algorithms like bubblesort
O(n^2)
time complexity of heapsort
O(n logn)
time complexity of mergesort
O (n logn)
time complexity of bubblesort
O(n^2)
time complexity of a linear search algorithm
O(n)
measures the amount of memory an algorithm needs to run as a function of the input size. it includes both the memory needed to store the input data and the memory neede for auxillary variables and data structures
space complexity
space complexity of a recursive algorithm
O(n)
