2.5 Complexity and Asymptotic Analysis

Question 1

Why do we capture order of growth?

Answer 1

exact counts are complicated
it is necessary to consider many different cases
there is no easy way to analyse sub-components and combine
Different compilers might affect the results

Question 2

What is big o notation?

Answer 2

Abstract programs in terms of how fast their running time grows with respect to their input size

Question 3

If g eventually dominates f…..

Answer 3

There exists k in N

∀(n:N) n>k → g(n) > f(n)

Question 4

if O(g) is the set of functions associated with g
is f in O(g) then.....

Answer 4

There exists C > 0 such that f is eventually dominated by C x g
f(n) ≤ Cg(n)

Question 5

Properties of Big O

Answer 5

f in O(f)
not necessarily symmetric
pre-order relation
O(1) ⊆ O(n)
O(n^m) ⊈ O(n^(m+1))
O(1) ⊈ O(log n) ⊈ O(n)

Question 6

What is a lower bound?

Answer 6

Any solution to that problem is at least that complex

Ω

Question 7

What is an algorithmic gap?

Answer 7

The problem lower bound complexity is less than the current best algorithms upper bound complexity

Question 8

What is space complexity?

Answer 8

Describes how much memory it requires to run. Often fixed. Often have more space than we have time.

Question 9

What is P = NP

Answer 9

Can every problem verifiable in Polynomial time also be solved quickly in polynomial time.

Question 10

What is a complexity class?

Answer 10

A set of functions with the same asymptotic complexity

Question 11

Examples of problems in P?

Answer 11

Calculating GCD
Determining if a number if prime
Member of a context free grammar

Question 12

Examples of problems in NP?

Answer 12

Boolean satisfiability
Factorisation into primes
Chinese postman
Graph colouring