2.3.1 Analysis, Design and Comparison of Algorithms

When developing an algorithm, what are the 2 things to check?

• Time complexity

• Space complexity

What is time complexity?

How much time is required to solve a particular problem

What is the Big O notation?

Shows the effectiveness of an algorithm

What is time complexity measured in?

Big O notation

What are the 6 different Big O notations?

• 0(1)

• 0(n)

• 0(n²)

• 0(nⁿ)

• 0(2ⁿ)

• 0(log n)

What is 0(1)?

Constant time complexity

What is constant time complexity?

The amount of time taken to complete an algorithm. It is independent from the number of elements inputted

What is 0(n)

Linear time complexity

What is linear time complexity?

The time taken to complete an algorithm is directly proportional to the number of elements inputted

What is 0(n²)

Polynomial time complexity

What is polynomial time complexity?

The amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n

What is 0(nⁿ)

Polynomial time complexity

What is 0(2ⁿ)

Exponential time complexity

What is exponential time complexity?

The amount of time taken to complete an algorithm will double with every additional item

What is 0(log n)

Logarithmic time complexity

What is logarithmic time complexity?

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted increase

What is space complexity?

The amount of storage an algorithm takes

How is space complexity expressed?

Big O (O(n)) notation

What happens when an algorithm makes a copy?

It stores extra data

What is an algorithm?

Series of steps that complete a task

How to reduce space complexity?

Make sure to perform all changes on the original pieces of data

How to reduce time complexity?

• Try to reduce the number of embedded loops

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

What is a linear search algorithm?

An algorithm which traverses through (accesses) every item one at a time until it finds the item it is searching for

What is the Big O notation for a linear search algorithm?

0(n)

What is a binary search algorithm?

A divide and conquer algorithm; splits the list into smaller lists until it finds the item it is searching for

What is the Big O notation of a binary search algorithm?

0(log(n))

What is the Big O notation of a bubble sort algorithm?

0(n²)