Week 7 - Algorithm Complexity & Concurrency Flashcards
What is an Algorithm?
An algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.
What is the design and analysis like in the algorithm?
Because even if all give correct results, we must select the best one based on certain criteria.
What is algorithm efficiency, and what resources are typically considered?
Algorithms efficiency refers to the resource usuage of an algorithm. The primary resources considered are:
- Time (runtime)
- Space (computer memory)
- Network Usuage
- Hardware Requirements
Efficiency often involves trade-ffs between the resources
How do we measure the run-time of an algorithm?
Run-time is measured through:
- Benchmarking on a representative set of inputs
- Analysing the algorithm’s time complexity to understand its performance across different input sizes.
What is the empirical analysis in algorithm efficiency, give an example.
The idea is that it implement the algorithm (a program) and time it.
Example way we can time the program:
Manual: Using a stopwatch
Auto: Using some timer function
What is time complexity, and how is it defined?
Time complexity refers to the number of operations an algorithm requires to execute, expressed as a function T(n), where n is the size of the input or problem.
What is the use of pseudocode?
Use pseudocode to remain independent of programming language and hardware.
What 3 key questions arise when analysing time complexity?
- What do we mean by operations? Basic computational steps like comparisons, assignments etc.
- What do we mean by size? The size of the input
- Which case do we analyse? Usually on worst-case scenario for robustness.
Examples of algorithms
Quadratic growth
F(n) = n^2
G(n) = n^2 -3n+2
Big-O Notation
What are some of common complexity classes of the Big-O notation?
◼O(1) = “Constant”
◼O(log2 n) = “Logarithmic”
◼O(n) = “Linear”
◼O(n log2 n) = “Log Linear”
◼O(n^2) = “Quadratic”
◼O(n^3) = “Cubic”
◼O(2^n) = “Exponential”
- Polynomial: O(n), O(n^2), O(n^3), … – “tractable”
- Exponential: O(n), O(n^2), O(n^3), … – “tractable”
How many operations needed for an algorithm?
With complexity T(n) = f(n) and input size n
How much time need for an algorithm?
Assuming 1 million operations per second
How do we determine the total complexities of an algorithm?
To determine the total algorithm complexity, consider the complexities of its components:
- Sequential algorithm phases: add the complexities of each phase
- Function/Method calls: Include the complexity of each function or method within the algorithm.
What are two main components to consider in total algorithm complexity?
- Sequential algorithm: Complexity accumulates as phases are executed one after another
- Function/method calls: Each call adds its own complexity,which must be accounted for
What is an example of sequential algorithm phases?
Matrix-vector multiplication: x=A b
Complexity: O(n) + O(n^2) = O(n^2)
- It presents the maximum of complexities
What is an example of function/method calls?
N array look-ups
Complexity: O(n) x O(long) = O(n log n)
- It represents the multiplication of complexities
What are some criteria for selecting the best algorithm?
Efficiency, simplicity, clarity, elegance, and proofs of correctness.
What key questions should we ask when analyzing an algorithm?
Is my algorithm correct? Does it always terminate?
What fundamental question might we need to ask before designing an algorithm?
Does an algorithm even existence for that problem?
What is meant by algorithm efficiency?
It refers to the resource usage of an algorithm, typically time (runtime) and space (memory).
Besides time and space, what other resources might an algorithm use?
Network usage, hardware requirements, and more.
