2.3.2 Standard algorithms

• How does linear search find a specific element in a list or array?

  Iterating one element at a time
• Steps in the binary search algorithm

  1️⃣ Set the search interval to the entire list

  2️⃣ Find the middle element of the current interval

  3️⃣ Compare the middle element to the target

  4️⃣ Narrow the search to the left or right half

  5️⃣ Repeat until the target is found or the interval is empty
• Binary search has a time complexity of O(log n).


  True
• Custom algorithms may not be as efficient or reliable as standard algorithms.
• Binary search repeatedly divides the search interval in half.
• Binary search is suitable for small datasets.

  False
• Binary search requires that the data is sorted
• Bubble sort is efficient for large datasets.

  False
• Insertion sort builds a sorted portion of the list by inserting elements from the unsorted portion into the correct position
• Insertion sort is efficient for large datasets.

  False
• Match the type of algorithm with its characteristic:

  Standard Algorithm ↔️ Optimized for performance

  Custom Algorithm ↔️ Tailored for unique needs
• What are standard algorithms designed to solve?

  Common programming problems
• Linear search is suitable for unordered data.


  True
• Binary search requires that the data be sorted.
• Match the algorithm type with its example:

  Sorting algorithm ↔️ Bubble sort

  Searching algorithm ↔️ Binary search

  Encryption algorithm ↔️ AES
• Reliability is a key advantage of standard algorithms.


  True
• Steps in the binary search algorithm

  1️⃣ Set the search interval to the entire sorted list

  2️⃣ Find the middle element of the current interval

  3️⃣ Compare the middle element to the target

  4️⃣ Narrow the search to the left or right half

  5️⃣ Repeat until the target is found or the interval is empty
• Binary search has a time complexity of O(log n)
• What is the time complexity of binary search?

  O(log n)
• Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order
• Match the sorting algorithm with its time complexity:

  Bubble Sort ↔️ O(n^2)

  Quick Sort ↔️ O(n log n)
• What is the time complexity of insertion sort?

  O(n^2)
• What is the key advantage of standard algorithms over custom algorithms?

  Optimized for performance
• Examples of standard algorithms include sorting algorithms, searching algorithms, and encryption algorithms.
• The time complexity of linear search is O(n).
• What are the key characteristics of standard algorithms?

  Efficiency and reliability
• What is the time complexity of linear search?

  O(n)
• Steps involved in binary search

  1️⃣ Set the search interval to encompass the entire sorted list.

  2️⃣ Find the middle element of the current interval.

  3️⃣ Compare the middle element with the target.

  4️⃣ If the middle element matches the target, return its index.

  5️⃣ If the middle element is greater than the target, narrow the search to the left half.

  6️⃣ If the middle element is less than the target, narrow the search to the right half.
• Binary search is simpler to implement than linear search.

  False
• Steps involved in bubble sort

  1️⃣ Start at the beginning of the list.

  2️⃣ Compare the first two elements.

  3️⃣ Swap them if they are in the wrong order.

  4️⃣ Move to the next pair of elements.

  5️⃣ Repeat until the end of the list.

  6️⃣ Repeat from the beginning until no swaps are made.
• Steps involved in insertion sort

  1️⃣ Start with the first element as the sorted portion.

  2️⃣ Iterate through the remaining unsorted elements.

  3️⃣ Compare each unsorted element to the sorted portion.

  4️⃣ Insert the unsorted element into the correct position in the sorted portion.

  5️⃣ Repeat until the entire list is sorted.
• Standard algorithms are well-known, tried-and-tested procedures designed to solve common programming problems
• Standard algorithms are less reliable than custom algorithms.

  False
• What is the time complexity of linear search?

  O(n)
• Which search algorithm has a lower time complexity for large datasets?

  Binary search
• What is the time complexity of linear search?

  O(n)
• Linear search iterates through each element until the target is found or the end is reached.
• How does bubble sort work to sort a list?

  Compares and swaps adjacent elements
• What does insertion sort build iteratively to sort a list?

  A sorted portion of the list
• How does selection sort find the next element to swap?

  Finds the minimum element