Yr 2 Big O Notation

Question 1

What are the two categories that algorithms are analysed on?

Answer 1

1. Time complexity
2. Memory/storage complexity

Question 2

Is big O the most efficient, average efficiency or least efficient case of an algorithm.

Answer 2

Represents the worst case (least efficient).

Question 3

What is the most efficient algorithm complexity (give an example).

Answer 3

O(1)
E.g. Hash tables

Question 4

State the order of efficiency from most to least efficient.

Answer 4

O(1) - constant time
O(logn) - logarithmic time
O(n) - linear time
O(nlogn ) - Quasilinear time
O(n^2) - quadratic time
O(2^n) - exponential time
O(n!) - factorial time

Question 5

What is the least efficient type of algorithm complexity (give an example)

Answer 5

Factorial time O(n!)
E.g. the heap

Question 6

Give an example of an algorithm that has quasilinear time complexity. And why is this the case?

Answer 6

O(nlogn)
Mergesort
Because for each item in the list the list must be split

Question 7

Give an example of an algorithm with time quadratic time complexity. And why is this the case?

Answer 7

O(n^2)
Bubble sort
Because the program loops through all list positions then for each list position loops through them all again