05 - Suitability of different Algorithms

 1. In order to decide which algorithm to chose over another, they are compared in terms of their efficiency: the _____ it takes to find the solution and the resources which are consumed in the process
Useful explanation of Big O with examples:





 2. Space-wise efficiency is referring to the amount of (memory) space the algorithm will take up before it terminates with the correct solution
Useful link for a complete overview, check out:



 3. When considering space-wise efficiency, the aim is to utilise data structures which take up ______________________

  the least inputs

  the least amount in memory

  the least outputs

  the most memory

 4. Example: populating a list with variables of type "real" will be ___________ inefficient, when it is clear that only whole numbers (integers) will ever be needed to solve the problem



  Big O


 5. This is the amount of time it takes for the algorithm to terminate with the correct solution

  Memory efficiency

  Time-wise efficiency

  Big O efficiency

  Space-wise efficiency

 6. Insertion Sort uses the insertion method and while it can perform at O(n) in the best case, it performs at O(n2) in the average and worst case.



 7. Consider the following algorithm: Count the number of computational steps in the algorithm
number1 <- INPUT

number2 <- INPUT

sum1 <- number1 + number2

number3 <- INPUT

sum2 <- sum1 + number3





 8. An ___________ algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases



  None of these options are valid

  O(log n)

 9. For a larger data set a linear search would be preferrable (more efficient or suitable) than a binary search.



 10. The Best Case represents the ________ speed the the algorithm can operate in in the most optimal conditions




  None of these options are valid

 11. The Worst Case represents the _______ speed that the algorithm will operate in in the worst conditions

  None of these options are valid




 12. The Average Case represents the average (or expected) speed the the algorithm will operate in in ______ conditions.


  None of these options are valid



 13. Fill in the blanks for the following excerpt
Some problems cannot be solved in polynomial time. 
Certain things are used in the world because of this. 
___________________________________ is a prime example. 

It is computationally hard to find two prime factors of a 
very large number. If it wasn't, we couldn't use the 
public key systems we use.

  Wireless Technology

  Quantum computing

  Simple addition and the finding of prime factors

  Public Key Cryptography

 14. The worst case scenario for a Bubble Sort is O(n)



 15. These are algorithms which provide close approximations for problems for which no known polynomial solution algorithm exists

  Quantum algorithms

  Intractable algorithms

  Tractable algorithms

  Approximation algorithms