2.3 Algorithms

Question 1

What are two things needed to be kept into mind when developing an algorithm?

Answer 1

-time complexity
-space complexity

Question 2

Explain time complexities? What are they known as?

Answer 2

-how much time an algorithm requires to solve a particular problem
-known as big-o notation, shows the effectiveness of the algorithm
-shows the amount of time taken relative to the number of data elements given as an input

Question 3

What is 0(1)?

Answer 3

-constant time complexity
-the amount of time taken to complete an algorithm is independent from the number of elements inputted

Question 4

What is 0(n)?

Answer 4

-linear time complexity
-the amount of time taken to complete an algorithm is directly proportional to the number of elements inputted

Question 5

What is 0(n^2)?

Answer 5

-polynomial time complexity
-the amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted

Question 6

What is 0(n^n)?

Answer 6

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

Question 7

What is 0(2^n)?

Answer 7

-exponential time complexity
-the amount of time taken to complete an algorithm will double with every additional item

Question 8

What is 0(log n)?

Answer 8

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

Question 9

What is 0(n log n)?

Answer 9

-logarithmic time complexity
-the time taken to complete an algorithm grows at a rate that is proportional to the number of elements inputted multiplied by the logarithm of n

Question 10

What time complexity should be used for algorithms using a ‘divide and conquer approach’?

Answer 10

log n
n log n

Question 11

What do we mean by space complexities? How can this be measured?

Answer 11

-the amount of storage the algorithm takes
-measured using big o-notation

Question 12

What are the best/average/worst cases for time complexities for bubble sort? Why?

Answer 12

best- 0(n)
as this is when array is already sorted

average- 0(n^2)
as this is when elements are randomly ordered

worst- 0(n^2)
as this is when the elements are sorted in reverse order

Question 13

What is the space complexity for bubble sort? Why?

Answer 13

0(1)
as it requires additional space for number of variables

Question 14

What are the best/average/worst cases for time complexities for insertion sort? Why?

Answer 14

best- 0(n)
as this is when array is nearly sorted

average- 0(n^2)
as this is when array is randomly sorted

worst- 0(n^2)
as this is when array is sorted in reverse order

Question 15

What is the space complexity for insertion sort? Why?

Answer 15

0(1)
as minimal extra space needed

Question 16

What are the best/average/worst cases for time complexities for merge sort? Why?

Answer 16

all- 0(n log n)
as the algorithm is being decomposed
–> log n, due to the number of separations becomes n log n

Question 17

What is the space complexity for merge sort? Why?

Answer 17

0(n)
as merge sort requires additional space for merging

Question 18

What are the best/average/worst cases for time complexities for quick sort? Why?

Answer 18

best- 0(n log n)
as this is when the pivot consistently divides array in half and is balanced

average- 0(n log n)
as this is when the pivot consistently divides array in half and is balanced

worst- 0(n^2)
as this is when the pivot consistently results in unbalanced partitions

Question 19

What is the space complexity for quick sort? Why?

Answer 19

0(log n)
as there is varying space depending on pivot and data

Question 20

What are the best/average/worst cases for time complexities for linear search? Why?

Answer 20

best- 0(1)
as this is when the target is at beginning of the list

average- 0(n)
as this is when the target can be randomly anywhere in the list, multiple iterations

worst- 0(n)
as this is when the target element is at the end of the list or not present

Question 21

What is the time complexity for linear search? Why?

Answer 21

0(1)
requires minimal space as nothing will be added or lost

Question 22

What are the best/average/worst cases for time complexities for binary search? Why?

Answer 22

best- 0(1)
as this is when the target is at the middle of the sorted list

average- 0(n log n)
as each comparison reduces the search space by 1/2

worst- 0(n log n)
as the target element could be at the beginning or end of the sorted list

Question 23

What is the space complexity for binary search? Why?

Answer 23

0(1)
no extra space needed

Question 24

What are the best/average/worst cases for time complexities for hash table search? Why?

Answer 24

best- 0(1)
when there are no collisions and the hash function distributes keys evenly

average- 0(1)
no collisions and a good hash function

worst- 0(n)
as this is when there are many collisions which leads to a linear search within the has table search

Question 25

What is the time complexity for a hash table search? Why?

Answer 25

0(n)
as additional space is required for the storage of collisions or key-value pairs

Question 26

What are the four sorting algorithms?

Answer 26

-bubble
-insertion
-merge
-quick

Question 27

Describe bubble sort

Answer 27

a sorting algorithm that repeatedly loops through the list comparing elements and swapping if they’re in the wrong order
passes through the list until sorted

Question 28

How does bubble sort work?

Answer 28

start from beginning of array
2. compare each pair of adjacent elements
3. if the elements are in the wrong order, swap them
4. repeat this process for each pair of adjacent elements in the array
5. after the first pass (passing through the whole array), repeat the whole process until a pass is made with no swaps

Question 29

When may using bubble sort be inefficient?

Answer 29

when there are large data sets

Question 30

Describe insertion sort

Answer 30

a sorting algorithm which places elements into a sorted sequence one element at a time

Question 31

How does insertion sort work?

Answer 31

1. start with second element of the array
2. compare the element with the one before it
3. if the previous element is greater, swap them
4. repeat this process until element is in its correct sorted position
5. move to next unsorted element and repeat steps 2-4 until the entire array is sorted

Question 32

What is insertion sort useful for?

Answer 32

-efficient for small datasets
-good for nearly sorted data

Question 33

Describe merge sort

Answer 33

-a divide and conquer sorting algorithm
divides the unsorted list into ‘n’ sub-lists containing one element, then uses recursion repeatedly merging sub-lists to produce sorted sub-lists until the whole array is recombined

Question 34

How does merge sort work?

Answer 34

uses two functions: MergeSort and Merge
mergesort- divides
merge- combines

1. divide the unsorted array until each element is by itself
2. repeatedly merge each element ordering each element with every merge until list is fully combined

Question 35

What is merge sort useful for?

Answer 35

efficient for large data sets

Question 36

Describe quick sort

Answer 36

-a divide and conquer sorting algorithm
-works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according whether they are less than or greater than the pivot

Question 37

How does quick sort work?

Answer 37

1. choose a pivot element from the array
2. partition the array into two sub arrays: elements less than the pivot and the other greater
3. process repeated recursively on each new sub array until all elements in the input are old pivots or form a list of 1 element

Question 38

What is quick sort useful for?

Answer 38

-efficient for large datasets
-pivot selection strategy influences performance

Question 39

What are the two searching algorithms?

Answer 39

-binary
-linear

Question 40

Describe binary search

Answer 40

an efficient sorting algorithm used to find the position of a target value within a sorted array or list

Question 41

How does binary search work?

Answer 41

only works on sorted data

1. find the middle element
2. compare elements on either side, unwanted half is discarded
3. repeat process until desired element is found or if it doesn’t exist in data set

Question 42

Describe linear search

Answer 42

a searching algorithm which examines each element in a list or array one by one until the target value is found or the entire list is traversed

Question 43

How does linear search work?

Answer 43

1. start from the first element in list
2. compare current element with target value, if successful return the index, if not, repeat with next element
3. repeat step two until target is found or the end of list is reached

Question 44

What is Dijkstra’s algorithm?

Answer 44

finds the shortest path between two nodes in a weighted graph

Question 45

What is A* algorithm?

Answer 45

a path-finding algorithm which adds on a heuristic value to improve efficiency of the process