3.1.2 Efficiency of algorithms

Cards (47)

  • What is an algorithm?
    A step-by-step procedure
  • Match the characteristic of an algorithm with its description:
    Finiteness ↔️ Must complete in a finite number of steps
    Definiteness ↔️ Each step must be clear and unambiguous
    Effectiveness ↔️ Should produce a correct result
    Input ↔️ May require input data
  • Time complexity is a measure of how long an algorithm takes to run as a function of the size of its input
  • Big O notation expresses the upper bound of an algorithm's time complexity.

    True
  • What is the Big O notation for constant time complexity?
    O(1)
  • Match the time complexity with its description:
    O(1) ↔️ Constant time - the algorithm takes the same amount of time regardless of input size
    O(log n) ↔️ Logarithmic time - the algorithm's runtime grows logarithmically with input size
    O(n) ↔️ Linear time - the algorithm's runtime grows linearly with input size
    O(n^2) ↔️ Quadratic time - the algorithm's runtime grows quadratically with input size
  • An algorithm with linearithmic time complexity has a Big O notation of O(n log n)
  • Understanding time complexity helps in choosing the most efficient algorithm for a problem.

    True
  • What does Big O notation measure in an algorithm?
    Upper bound of time
  • Match the Big O notation with its description:
    O(1) ↔️ Constant time - the algorithm takes the same amount of time regardless of input size
    O(log n) ↔️ Logarithmic time - the algorithm's runtime grows logarithmically with input size
    O(n) ↔️ Linear time - the algorithm's runtime grows linearly with input size
    O(n^2) ↔️ Quadratic time - the algorithm's runtime grows quadratically with input size
  • Constant time is denoted as O(1)
  • An algorithm with constant time takes the same amount of time regardless of input size
  • Order the following time complexities from fastest to slowest:
    1️⃣ O(1)
    2️⃣ O(log n)
    3️⃣ O(n)
    4️⃣ O(n log n)
    5️⃣ O(n^2)
  • Big O notation is used to describe the lower bound of an algorithm's time complexity
    False
  • An algorithm with logarithmic time complexity grows logarithmically with input size
  • What does linearithmic time complexity grow with?
    Input size and its logarithm
  • Searching for an element in a list has a time complexity of O(n)
  • Algorithms with linear time complexity are generally more efficient than those with polynomial time complexity for larger input sizes
  • Space complexity measures the memory an algorithm requires as a function of input size
    True
  • What is an example of an algorithm with constant space complexity?
    Finding the maximum in an array
  • An algorithm must complete in a finite number of steps

    True
  • What is an algorithm defined as?
    A step-by-step set of instructions
  • Finiteness in algorithms means they must complete in a finite number of steps
  • Linear time complexity, O(n), means the runtime increases linearly
  • An algorithm with O(n) complexity is highly efficient for large datasets because each element requires constant time.
    True
  • What is space complexity a measure of?
    Memory required by an algorithm
  • Creating a copy of an array with n elements has a space complexity of O(n)
  • What does Big O notation help us understand about an algorithm's performance?
    How it scales with input size
  • An algorithm can be compared to a recipe for baking a cake.

    True
  • An algorithm is a step-by-step set of instructions for solving a problem
  • Steps to find the largest number in a list
    1️⃣ Start with the first number as the largest.
    2️⃣ Go through each number in the list.
    3️⃣ If a number is greater than the current largest, update the largest.
    4️⃣ Return the largest number.
  • Big O notation is used to express the best-case scenario for an algorithm's time complexity.
    False
  • The Big O notation expresses the upper bound of an algorithm's time complexity.
  • Time complexity is a measure of how long an algorithm takes to run as a function of the size of its input
  • Big O notation expresses the upper bound of an algorithm's time complexity

    True
  • Match the time complexity with its description:
    O(n log n) ↔️ Linearithmic time
    O(n^2) ↔️ Quadratic time
  • Time complexity classes group algorithms based on how their runtime grows with input size
    True
  • Binary search in a sorted array has a logarithmic time complexity

    True
  • What is an example of a polynomial time algorithm?
    Nested loops over an array
  • An algorithm is a step-by-step set of instructions for solving a problem