Structured Algorithms

Question 1

Explain

‘Big O’ complexity chart

Answer 1

A graph that shows the efficiency of algorithms by plotting the number of operations required to sort a given number of elements in the worst-case scenario (i.e. the target number is the last number to be found)

it shows how performance scales with input size

Question 2

Explain

‘Big O’ notation

(time complexity)

Answer 2

A measure of how fast an algorithm runs based on the size of its input.

O(n) means algorithm speed grows at the same rate as its input size.

Question 3

Recall

The two search algorithms.

LB

Answer 3

• Linear Search
• Binary Search

Question 4

Explain

What occurs in the linear search algorithm?

Answer 4

An array is iterated through in index order until the target is found.

Question 5

Explain

What occurs in the binary search algorithm?

halves sort

Answer 5

• If middle number > target number, reiterate for the lower half of the array (excluding the middle number)
• If middle number < target number, reiterate for the higher half of the array (excluding the middle number)

repeats and halves search area until target is found

note that binary search requires the array to be sorted.

Question 6

Recall

The three sort algorithms.

BIS

Answer 6

• Bubble Sort
• Insertion Sort
• Selection Sort

Question 7

Explain

What occurs in the bubble sort algorithm?

Answer 7

• i and i + 1 of an array are iterated over.
• if array[i] > array [i+1], swap them around.

Repeats in passes over the whole array until everything is swapped correctly.

Question 8

Explain

What occurs in the insertion sort algorithm?

Answer 8

no clue bro

Question 9

Explain

What occurs in the selection sort algorithm?

Answer 9

• Iterates and finds the maximum value of the list, and moves it to the end of the list, working backwards.

Repeats in passes over the whole array until everything is swapped correctly.

Question 10

Recall

All sorting algorithms (that we’re required to know) have a time complexity of?

Answer 10

O(n²)

(this is not good, and gets geometrically slower as #elements increases)

Question 11

Recall

What is the time complexity of the binary search algorithm?

Answer 11

O[log(n)]

(this is very good, but it requires the data to be sorted first.)

Question 12

Recall

What is the time complexity of the linear search algorithm?

Answer 12

O(n) ☹️

this is okay but not ideal and gets slower with larger databases