Preview

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 increases as the input n decreases

  O stays the same with input n

  O decreases with input n

  O increases with input n

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

  O(n)

  O(n!)

  O(1)

  O(log2n)

 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(log2n)

  O(1)

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

  O(n)

  O(1)

  O(n!)

  O(log2n)

 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(log2n)

  O(n)

 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
formula_inconsequential_parts.png

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

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

  5n will increase much faster than the rest

  2n will decrease rapidly

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

  FALSE

  TRUE

 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).

  TRUE

  FALSE

 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(n)

  O(1)

  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!+1)

  O((n+1)!)

  O(1)

  O(n)

 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
      return total

  an O(1) function

  an O(n) function

  an O(2) function

  an O(n!) 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)

  TRUE

  FALSE


Report an error