krit.club logo

The World of Algorithms - Improving the Algorithm

Grade 9CBSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

Algorithm Efficiency: This refers to the amount of resources (time and memory) that an algorithm uses. Improving an algorithm means reducing the number of steps (nn) or the memory used.

•

Time Complexity: A measure of the number of operations performed by an algorithm as a function of the input size nn. Common complexities include O(n)O(n) (linear) and O(log⁡n)O(\log n) (logarithmic).

•

Linear Search: An algorithm that checks every element in a list until the target is found. In the worst case, it takes nn steps for a list of size nn.

•

Binary Search: A much faster algorithm for sorted lists. It repeatedly divides the search interval in half. It takes approximately log⁡2n\log_{2} n steps.

•

Bubble Sort Improvement: A standard bubble sort takes n(n−1)/2n(n-1)/2 comparisons. We can improve it by adding a flag to check if any swaps occurred; if no swaps occur in a pass, the list is already sorted.

•

Nested Loops: Algorithms with nested loops (like Bubble Sort) often have a complexity of O(n2)O(n^2), meaning if the input size doubles, the time taken increases by four times (22=42^2 = 4).

📐Formulae

Maximum steps in Linear Search=n\text{Maximum steps in Linear Search} = n

Maximum steps in Binary Search≈log⁡2(n)\text{Maximum steps in Binary Search} \approx \log_{2}(n)

Total comparisons in Bubble Sort (Worst Case)=n(n−1)2\text{Total comparisons in Bubble Sort (Worst Case)} = \frac{n(n-1)}{2}

Middle index in Binary Search=⌊low+high2⌋\text{Middle index in Binary Search} = \lfloor \frac{\text{low} + \text{high}}{2} \rfloor

💡Examples

Problem 1:

Compare the number of steps required to find a number in a sorted list of n=1024n = 1024 elements using Linear Search and Binary Search.

Solution:

  1. For Linear Search, the maximum number of steps is equal to the number of elements nn. Stepslinear=1024\text{Steps}_{\text{linear}} = 1024

  2. For Binary Search, the maximum number of steps is log⁡2n\log_{2} n. Stepsbinary=log⁡2(1024)\text{Steps}_{\text{binary}} = \log_{2}(1024) Since 210=10242^{10} = 1024, then: log⁡2(1024)=10\log_{2}(1024) = 10

  3. Improvement Ratio: 102410=102.4\frac{1024}{10} = 102.4 Binary search is more than 100100 times faster in the worst case for this list size.

Explanation:

Linear search grows linearly with the size of the data, while binary search grows logarithmically, making it significantly more efficient for large datasets.

Problem 2:

Calculate the total number of comparisons needed to sort a list of n=10n = 10 elements using the standard Bubble Sort algorithm.

Solution:

The number of comparisons is given by the formula n(n−1)2\frac{n(n-1)}{2}. Given n=10n = 10: Comparisons=10×(10−1)2\text{Comparisons} = \frac{10 \times (10 - 1)}{2} Comparisons=10×92\text{Comparisons} = \frac{10 \times 9}{2} Comparisons=902\text{Comparisons} = \frac{90}{2} Comparisons=45\text{Comparisons} = 45

To visualize the addition of comparisons per pass (9+8+7+6+5+4+3+2+19 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1): 98765432+145\begin{array}{r} 9 \\ 8 \\ 7 \\ 6 \\ 5 \\ 4 \\ 3 \\ 2 \\ + 1 \\ \hline 45 \end{array}

Explanation:

In each pass of the Bubble Sort, the number of comparisons decreases by 1 because the largest element 'bubbles up' to its correct position.