2.3.1 analysis, design and comparison algorithms

time complexity

how much time an algorithm requires to solve a particular problem

big o cheat sheet

O(1) time complexity

• constant time complexity

• time taken is independent from the number of elements inputted

O(n) time complexity

• linear time complexity

• time taken is directly proportional to the number of elements inputted

O(n²) time complexity

• time taken is directly proportional to the square of the elements inputted

• quadratic

0(2ⁿ)

• exponential

• time taken will double with every additional item

0(log n)

• logarithmic

• each step cuts the problem size in half

0(n log n)

• linearithmic

• the algorithm does n operations, but each operation takes log n time, so the total is n × log n steps

time complexities in order

fastest

• O(1)

• O(log n)

• O(n)

• O(n log n)

• O(n²)

• O(2ⁿ)

• O(n!)

space complexity

the amount of storage the algorithm takes

in place sort

• elements of the array are sorted directly within the array itself

• space complexity remains O(1)

• Bubble Sort, Insertion Sort, quick sort

out of place sort

• additional arrays are used as part of the sort requiring more memory

• O(n)

• e.g. the sub-arrays created during merge sort

reduce space complexity

preforms all the changes on the original piece of data

reduce time complexity

• reduce the number of embedded loops

• reduce the number of items you have to complete the operations on

algorithm

a series of steps that completes a task

linear search

• starts at the first item in the list and checks each item one by one

• doesn’t require data to be in order

• can be efficient for small data sets

• inefficient for large data sets

linear search in pseudocode

linear search in python

binary search

• starts at the middle item in the list and repeatedly divides the list in half

• each time checking if the midpoint is the item being searched for

• discarding half of the data after each iteration, quickly reducing large data sets

• requires the data set to be sorted

• efficient for large data sets

binary search in pseudocode

binary search in python