2.3.1 Algorithms

Question 1

Big O Notation

Answer 1

Big O Notation : Evaluates the complexity (measure of efficiency) of the algorithm

• Evaluates the worst case scenario for the algorithm
• States how the memory, time and recourses increases as data increases
• A useful approximation of the time taken to execute an algorithm for a given number of items in a data set.
• Remove constants and only leave dominant term

Question 1

Time complexity

Answer 1

Time complexity : Estimates increase in Time required to solve a problem as the problem scales.
- Measured with Big O notation
- Heuristic as many variables affect speed

Question 2

All types of Time Complexities and examples

Answer 2

O(1) - Constant Time Complexity : Time taken to completion independent to data input - constant so most efficient
e.g. Hash function

O(n) - Linear Time Complexity : Time taken to completion directly proportional to number of data items.
e.g. Linear Search

O(n^k) - Polynomial Time Complexity : Time taken to completion proportional to number of data items to the power of k.
e.g. Quadratic time complexity - Bubble sort is O(n^2)

O(2^n) - Exponential time Complexity : Time taken to completion doubles with each additional item added.
e.g. Recursive algorithms that solve two problems size N-1, like Fibonacci sequence (almost : n-1 and n-2)

O(log(n)) - Logarithmic time complexity : Rate Time taken to completion increases by decreases as more data items are added.
e.g. Divide and conquer algorithms like Binary Sort

O(nlog(n)) - Linearithmic
Merge sort or quick sort

Question 3

Space Complexity

Answer 3

Space complexity : How much more Memory an algorithm takes up as algorithm scales.
- Measured with big O notation
- Algorithms that make many copies store more data which is expensive

Question 4

Bubble Sort

Answer 4

Bubble Sort : Passes through list Comparing adjacent elements and swapping if in incorrect order until end of the list then goes back to start.
- One item sorted per pass
- Maximum n-1 passes
- Use flag that terminates algorithm if no swaps made (data sorted) to increase efficiency
- Decrementing the inner loop so don’t check items already sorted
- And can go from either direction

Time Complexity :
Worst Case : O(n^2) (data in reverse order)
Average Case : O(n^2)
Best Case : O(n) (data already sorted)

Space Complexity :
O(1) as in place algorithm

Question 5

Insertion Sort

Answer 5

Insertion Sort : makes the first item sorted and then sorts one item at a time from unsorted list into the sorted list by comparisons linearly.
- Shifts data forward one then inserts data in
- Sorts one data item at a time
- Slightly more efficient that bubble sort

Time Complexity :
Worst Case : O(n^2) (data in reverse order)
Average Case : O(n^2)
Best Case : O(n) (data already sorted)

Space Complexity :
O(1) as in place algorithm

Question 6

Merge Sort

Answer 6

Merge Sort : Splits data input in half recursively until all are of size 1
- Recombines sub lists in pairs placing into correct order repeatedly until single ordered list left
- Divide and Conquer Algorithm
- Consistent time complexity

Time Complexity :
Worst case : O(nlog(n))
Average case : O(nlog(n))
Best case : O(nlog(n))

Space Complexity :
O(n)

Question 7

Quick Sort

Answer 7

Quick Sort : Uses divide and conquer to

• Highlight first element as start pointer and last list element as end pointer
• Repeatedly compare numbers being pointed to:
  If incorrect , swap and move end pointer
  Else move start pointer
• Split list into two lists around end pointer (greater than end pointer to the right, less than to the left)
• Quick sort each sublist
• Repeat until all sublists only one number
• Combine sublists

Time Complexity :
Worst case : O(n^2)
Average case : O(nlog(n))
Best case : O(nlog(n))

Space Complexity :
O(log(n))

Question 8

Linear Search

Answer 8

Linear Search : Searches through every value in order from the first order sequentially checking if equal to data, if yes then report found else go to next item until item found (return found) or at end of list (return not in list).
- Very basic and easy to implement
- Does not require data to be sorted
- More inefficient than binary on average (unless item to be found is at start)

Time Complexity :
Worst case : O(n) (at end of list)
Average case : O(n)
Best case : O(1) (in first element)

Question 9

Binary Search

Answer 9

Binary search -
Uses Divide and conquer
- Only works on sorted data.

Process :
- Defines LB and UB pointers
- Calculate Midpoint with (LB + (LB - UB DIV 2))
- Go to index and compare to input
If equal return index and true
else if input larger set LB = index+1
else if input smaller set UB = index-1
- Repeat calculating midpoint of new sub list and comparing until LB >= UB

Repeated until desired element found or determined to not be in list,
- Discards half of input data each iteration – very efficient

Time Complexity :
Worst case : O(log(n))
Average case : O(log(n))
Best case : O(1)

Question 10

Dijkstras Algorithm

Answer 10

Dijkstras Algorithm : Pathfinding Algorithm to calculate the shortest path between two nodes on a weighted graph.
- Finds all routes to all destination nodes, not just one.

• Visits next smallest working value.
• Stops when destination node has smallest working value.
• Always finds shortest path.

Question 11

A* Algorithm

Answer 11

A* Algorithm : Pathfinding Algorithm to calculate the shortest path between two nodes on a weighted graph using Heuristics.
- Adds actual cost to heuristic cost to calculate working value
- Doesn’t have to find every possible solution - much more efficient (especially on large graph).

• Doesn’t always find shortest path if heuristic inaccurate and overestimates cost.
• Heuristic calculation takes time
• Effectiveness largely dependent on accuracy of heuristic algorithm.