2.3.1: analysis, design and comparison of algorithms

avatar
Created by
Fiona Bull

Cards (18)

  • What two pieces of information allow you to analyse an algorithm?
    • Time Complexity
    • Space Complexity
  • What is meant by the time complexity of an algorithm?

    The amount of time required to solve a particular problem
  • How do you measure of the time complexity?
    Big-O notation
  • What does the Big-O notation show?

    The effectiveness of an algorithm
  • What is the Big-O notation good for?
    It allows you to predict the amount of time taken to solve an algorithm given the number of items stored
  • What does a linear time complexity mean?
    The amount of time taken to complete an algorithm is independent from the number of elements inputted.
  • What does a constant time complexity mean?
    The amount of time taken to complete an algorithm is independent to the number of inputted elements
  • What does a polynomial time complexity mean?
    The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n
  • What does an exponential time complexity mean?
    The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.
  • What does a logarithmic time complexity mean?
    The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.
  • What is a logarithm?
    How many times a certain number (base) is multiplied together to reach another number.
  • What is space complexity?
    The space complexity is the amount of storage space an algorithm takes up
  • What is an algorithm?

    An algorithm is a series of steps that complete a task
  • How do you reduce the space complexity?
    Try to complete all of the operations on the same data set
  • How do you reduce the time complexity of an algorithm?
    You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer
  • What is the Big-O notation of a linear search algorithm?
    O(n)
  • What is the Big-O notation of a binary search algorithm?
    O(log(n))
  • What is the Big-O notation of a bubble sort algorithm?
    O(n^2 )