# 03 - Maths for Big O Notation

1. An O function has an order. In this context, the order quantifies how rapidly ____________________ and the shape of that increase.

O decreases with input n

O increases with input n

O increases as the input n decreases

O stays the same with input n

2. _______means that the algorithm performance is constant and does not depend on n

O(1)

O(log2n)

O(n!)

O(n)

3. ________ is when the algorithm is factorial n and is extremely sensitive to the input size and it rapidly becomes impractical.

O(n!)

O(n)

O(1)

O(log2n)

4. ____ is when the algorithm performance changes linearly with n. The FOR loop example is of order O(n).

O(log2n)

O(n!)

O(n)

O(1)

5. A binary search algorithm to find an item in an ordered array is of this order. This is not so good as linear

O(1)

O(n)

O(n!)

O(log2n)

6. One of these parts __________________ This is the dominant effect of the algorithm. When converted to Big O notation, this is the only part that matters, and the rest will be discarded

5n will increase much faster than the rest

2n will decrease rapidly

2n+3, will increase much faster than the rest

n to the power of 3 will increase much much faster than the rest.

7. In general, you want your program to have as little complexity as possible, so it executes quickly

TRUE

FALSE

8. You lost your wedding ring on the beach, and have no memory of when or where it was lost. The big-O performance of your ring finding algorithm will be O(L)
```You decide to do a brute force grid search with your metal detector,
where you divide the beach into strips, and walk down every strip,
scanning the whole beach, until you find it.

For simplicity, assume
the beach is a square of side length L  meters, each of your strips has
a constant width of 1 meter, and it takes 10 seconds to walk 1 meter
(it's hard to walk while searching).```

FALSE

TRUE

9. Determine the running time in Big O notation of the second algorithm (Algorithm 2)
```Consider the following two algorithms to print all permutations of
1,2,3.....nthat are strictly increasing:

Algorithm 1:
============
Check each permutation on whether it's sorted or not, and print
each one that is sorted.

Algorithm 2:
=============
The only such permutation is 1,2,3,........n, so just print it.
```

O(1)

O(n)

O(n!+1)

O((n+1)!)

10. Determine the running time in Big O notation of the first algorithm (Algorithm 1)
```Consider the following two algorithms to print all permutations of
1,2,3.....nthat are strictly increasing:

Algorithm 1:
============
Check each permutation on whether it's sorted or not, and print
each one that is sorted.

Algorithm 2:
=============
The only such permutation is 1,2,3,........n, so just print it.```

O(n)

O((n+1)!)

O(1)

O(n!+1)

11. O(1) is a linear-time algorithm runs in time proportional to the input

FALSE

TRUE

12. The following code is an example of:
```  def count_ones(a_list):
total = 0
for element in a_list:
if element == 1:
total += 1

an O(n!) function

an O(1) function

an O(n) function

an O(2) function

13. This is the holy grail of scalability. With an O(n) algorithm, you can increase your inputs forever and never bog down.

FALSE

TRUE

14. For the following example, in Big O terms it would be: O(N)
```For example, suppose we write a script that sends out one email
to each person on a list. Suppose it takes us 100 steps to create
each person's email, and 200 steps to connect to a server and
send them all. So if we have N people to send to, it will take us
(100 * N) + 200 steps to finish the job.```

TRUE

FALSE

15. For a problem of size N: a linear-time algorithm is "order N": O(N)

FALSE

TRUE