2.3 Algorithms Flashcards

1
Q

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

A

-time complexity
-space complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Explain time complexities? What are they known as?

A

-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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is 0(1)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is 0(n)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is 0(n^2)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is 0(n^n)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is 0(2^n)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is 0(log n)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is 0(n log n)?

A

-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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

log n
n log n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the space complexity for bubble sort? Why?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the space complexity for insertion sort? Why?

A

0(1)
as minimal extra space needed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the space complexity for merge sort? Why?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the space complexity for quick sort? Why?

A

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

20
Q

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

A

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

21
Q

What is the time complexity for linear search? Why?

A

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

22
Q

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

A

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

23
Q

What is the space complexity for binary search? Why?

A

0(1)
no extra space needed

24
Q

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

A

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

25
What is the time complexity for a hash table search? Why?
0(n) as additional space is required for the storage of collisions or key-value pairs
26
What are the four sorting algorithms?
-bubble -insertion -merge -quick
27
Describe bubble sort
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
28
How does bubble sort work?
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
29
When may using bubble sort be inefficient?
when there are large data sets
30
Describe insertion sort
a sorting algorithm which places elements into a sorted sequence one element at a time
31
How does insertion sort work?
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
32
What is insertion sort useful for?
-efficient for small datasets -good for nearly sorted data
33
Describe merge sort
-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
34
How does merge sort work?
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
35
What is merge sort useful for?
efficient for large data sets
36
Describe quick sort
-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
37
How does quick sort work?
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
38
What is quick sort useful for?
-efficient for large datasets -pivot selection strategy influences performance
39
What are the two searching algorithms?
-binary -linear
40
Describe binary search
an efficient sorting algorithm used to find the position of a target value within a sorted array or list
41
How does binary search work?
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
42
Describe linear search
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
43
How does linear search work?
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
44
What is Dijkstra's algorithm?
finds the shortest path between two nodes in a weighted graph
45
What is A* algorithm?
a path-finding algorithm which adds on a heuristic value to improve efficiency of the process