2. 3. 1 Analysis, Design and Comparison of Algorithms Flashcards
1
Q
Analysis of algorithms
A
- Two things need to be checked when developing an algorithm, Time and Space complexity
2
Q
Time complexity
A
- How much time it requires to solve a particular problem, measured using big-o notation, shows effectiveness of an algorithm
- Shows upper limit for amount of time taken relative to number of data elements given as input
- Allows us to predict amount of time it takes for algorithm to finish given number of data elements
- Graphs helpful for showing relationships between time and number elements inputted
3
Q
Big-o notation
A
- Written in form O(n), demonstrates relationship between number of inputted entities (n) and the time relationship (O(n))
- O(1), Constant time complexity, amount of time taken to complete algorithm is independent from number of elements inputted (does not matter how many elements inputted, same time)
- O(n), Linear time complexity, amount of time taken to complete algorithm is directly proportional to number of elements inputted (time increases as number of elements increases)
- O(n^2), Polynomial time complexity, amount of time taken to complete algorithm is directly proportional to square of elements inputted
- O(2^n), Exponential time complexity, amount of time taken to complete algorithm will double every additional time (increment)
- O(log n), Logarithmic time complexity, time taken to complete algorithm increases at smaller rate as number of elements is inputted
- Order of best to worst time complexities for algorithms shown in image (Ignore O(n log(n)) it is not on the spec)
4
Q
Algorithm examples of Big-o notation
A
View the image, state what notation to use and why, multiple Time complexities can be seen within the algorithm, we take the one with the largest factor or exponent
5
Q
Graphs for each Time complexity
A
State what time complexity is represented by each of the graphs
6
Q
Logarithms
A
It is the inverse of an exponential, an operation that determines how many times a certain number (base) is multiplied by itself to reach another number
7
Q
Space Complexity
A
- The amount of storage the algorithm takes, commonly expressed using Big O notation
- Algorithm stores extra data whenever it makes a copy, this isn’t ideal when working with lots of data due to the fact that this will take lots of storage which is expensive
8
Q
Analysing algorithms based on Time and Space Complexity
A
- T and S Complexity very important when analysing effectiveness of program
- No priority for either, up to you at the design stage when creating the algorithm which one is of more importance
9
Q
Designing Algorithms
A
- Algorithm is a series of steps/instructions to complete a task
- Main objective of A is to complete the task, the next objectives is to get the best T and S complexity
- Minimising T and S complexity is heavily dependent on your situation, which one do you believe is of more importance is the question you ask yourself
- In the case of developing an algorithm with the main goal of manipulating data in a large database
- If you have lots of data but require it to be processed quickly, you would pay more attention to T rather than S complexity
- If you have a lot of processing power, T complexity not as important, would instead focus on S complexity, make sure you aren’t wasting lots of data often
- To reduce S complexity, changes must be performed on original pieces of data
- To reduce T complexity, try reduce num of items that operations need to be performed on
- For example, divide and conquer algorithm reduces the num of items after each iteration, results in logarithmic time complexity (2nd best)
10
Q
Comparison of Algorithms
A
Board compares T complexity mostly, occasionally mentions S complexity, just have understanding that smaller S complexity, better algorithm, always consider the worst-case scenario when comparing
11
Q
Searching Algorithms
A
- Linear Search Algorithm and Binary Search Algorithm
12
Q
Linear Search Algorithm
A
- Traverse through every item one at a time till it finds items its searching for, Big-O notation is O(n) (Linear Time Complexity)
- Has a single while loop, reason why it is a Linear Time Complexity Algorithm
- It is therefore suitable for a small number of items
- It can be implemented using an array or linked list
13
Q
Binary Search Algorithm
A
- Divide and Conquer algorithm, splits list (divide) into smaller lists till it finds the item it’s looking for (conquer)
- Size of list is halved every time, for this reason it’s Big-O notation is O(log(n)) (Logarithmic Time Complexity)
- It is therefore suitable for a large number of items
- It can be implemented using an array or binary tree
14
Q
Sorting Algorithms
A
Bubble sort, Merge sort, Insertion sort and Quick sort
15
Q
Bubble Sort Algorithm
A
- Evaluates pairs of items from left to right, ensures larger value is above smaller value
- It has a polynomial Big-O notation O(n^2)
