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
    See similar decks