Week 7 - Algorithm Complexity & Concurrency

Question 1

What is an Algorithm?

Answer 1

An algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.

Question 2

What is the design and analysis like in the algorithm?

Question 3

What is algorithm efficiency, and what resources are typically considered?

Answer 3

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

Question 4

How do we measure the run-time of an algorithm?

Answer 4

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.

Question 5

What is the empirical analysis in algorithm efficiency, give an example.

Answer 5

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

Question 6

What is time complexity, and how is it defined?

Answer 6

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.

Question 7

What is the use of pseudocode?

Answer 7

Use pseudocode to remain independent of programming language and hardware.

Question 8

What 3 key questions arise when analysing time complexity?

Answer 8

1. What do we mean by operations? Basic computational steps like comparisons, assignments etc.
2. What do we mean by size? The size of the input
3. Which case do we analyse? Usually on worst-case scenario for robustness.

Question 9

Examples of algorithms

Question 10

Quadratic growth

Answer 10

F(n) = n^2
G(n) = n^2 -3n+2

Question 11

Big-O Notation

Question 12

What are some of common complexity classes of the Big-O notation?

Answer 12

◼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”

Question 13

How many operations needed for an algorithm?

Answer 13

With complexity T(n) = f(n) and input size n

Question 14

How much time need for an algorithm?

Answer 14

Assuming 1 million operations per second

Question 15

How do we determine the total complexities of an algorithm?

Answer 15

To determine the total algorithm complexity, consider the complexities of its components:

1. Sequential algorithm phases: add the complexities of each phase
2. Function/Method calls: Include the complexity of each function or method within the algorithm.

Question 16

What are two main components to consider in total algorithm complexity?

Answer 16

1. Sequential algorithm: Complexity accumulates as phases are executed one after another
2. Function/method calls: Each call adds its own complexity,which must be accounted for

Question 17

What is an example of sequential algorithm phases?

Answer 17

Matrix-vector multiplication: x=A b

Complexity: O(n) + O(n^2) = O(n^2)
- It presents the maximum of complexities

Question 18

What is an example of function/method calls?

Answer 18

N array look-ups

Complexity: O(n) x O(long) = O(n log n)
- It represents the multiplication of complexities