Algorithm Complexity

Question 1

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

Answer 1

Empirical analysis (benchmarking on representative set of inputs)

Analyse the (time) complexity

Question 2

Empirical analysis

Answer 2

Implement the algorithm (a program) and time it

Question 3

How can we time a program?

Answer 3

Manual - using a stopwatch

Automatic - using some timer function

Run the program for various input sizes and measure run time

Question 4

Time Complexity

Answer 4

the number of operations that an algorithm requires to execute in terms of the size of the input or problem.

usually focusing on worst-case analysis

Question 5

O(1)

Answer 5

Constant time - Input size does not matter
Usually better than linear

On a graph this will show up as a straight line

Extremely fast

Question 6

O(log n)

Answer 6

Logarithmic

Binary search

As the data size increases this algorithm becomes more and more efficient compared to the early stages with the smaller data set.

Get the middle element of the array when looking for a value see if it is smaller of bigger and look to the relevant half accordingly

Question 7

O(n log2 n)

Answer 7

Log Linear

Question 8

O(n^2)

Answer 8

Quadratic time complexity
the runtime is proportional to the square of the input size

Common in nested loops

As the amount of data increases it is going to take increasingly more and more time to complete anything that has a runtime

Extremely slow with large data (slower than linear) but can be faster in the case of a smaller data set

Question 9

O(n3) =

Answer 9

Cubic time complexity

The runtime is proportional to the cube of the input size

Common in algorithms with three nested loops

Question 10

O(^2n) =

Answer 10

Exponential time complexity; the runtime doubles with each additional input sizes

Question 11

Look up a value v in a sorted array

Answer 11

Search from the middle, if the number is smaller we focus on the right hand side of the array

This is a way to get rid of half of the array

Question 12

Big O notation

Answer 12

Simplified analysis of an algorithm’s efficiency

Question 13

Types of measurement for an algorithm’s efficiency

Answer 13

Worst-case
Best-case
Average-case

Question 14

0(1)

Answer 14

Constant

Input size does not affect the time of completion

Question 15

0(n)

Answer 15

Linear time

As the amount of data increases, the amount of steps increases proportionally

Question 16

What is the purpose of analysing Big O Notation?

Answer 16

To predict the scalability and efficiency of an algorithm as the input grows

Question 17

What is the difference between best case and worse case complexity

Answer 17

Best-case = the minimum time complexity for any input

Worst-case = the maximum

Question 18

Logarithmic Time Complexity
Why is it considered more efficient?

Answer 18

Runtime increases very slowly even for large input sizes

Common in divide-and-conquer algorithms

Question 19

What is the Big O complexity for finding the maximum value in an unsorted array?

Answer 19

O(n) linear complexity

Question 20

Exponential time

Answer 20

O(2n)

Runtime doubles with each additional input element

Extremely rapid

Impractical for large inputs, typically avoided

Grows much faster than O(n3) and O(n2)

T(n)=2^n or K^n where K>1

Question 21

Cubic Time

Answer 21

O(n3)

Slower than exponential but faster than quadratics

Can handle moderately large inputs but is inefficient for very large inputs

T(n)=n^3

Question 22

Quadratic Time

Answer 22

O(n2) grows at a manageable rate and is often feasible for medium to large data sets

T(n)=n^2

Question 23

Linear Time

Answer 23

Runtime grows directly proportional to n

Slow growth

T(n)=n

Question 24

Constant time

Answer 24

Runtime remains constant regardless of input size

No growth, constant for all data

T(n)=c (constant value)

Question 25

K>1

Answer 25

K is the base in exponential growth K^n

K>1 ensures the true exponential growth occurs

K=1 would lead to a constant function

K<1 would result in an exponential decay