Section 8 Chapter 45 - Big-O Notation

Question 1

What is a function in terms of mappings

Answer 1

It is a mapping from one set of values to another set of values (the domain to the co-domain)

Question 2

Time complexity

Answer 2

The time that an algorithm takes to complete

Question 3

Permutations

Answer 3

All the different ways of arranging a set of objects

Question 4

Number of permutations

Answer 4

n!

Question 5

How to express constant time with Big O notation

Answer 5

O(1)

Question 6

How to express linear time with Big O notation

Answer 6

O(n)

Question 7

How to work out the time complexity of a function

Answer 7

Look for the most important term (ignore all coefficients)

Question 8

How to work out the time complexity of an algorithm

Answer 8

X nested for loops means complexity n^X
Splitting the search space into pieces is log(n)
Checking permutations is n!