krit.club logo

The World of Algorithms - Data Structures

Grade 9CBSE

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

🔑Concepts

•

An algorithm is a step-by-step procedure to solve a problem in a finite number of steps with a definite starting and ending point.

•

Data Structures are systematic ways of organizing and storing data so that it can be used efficiently (e.g., Arrays, Lists, Stacks, Queues).

•

Time Complexity T(n)T(n) refers to the amount of time an algorithm takes to run as a function of the input size nn.

•

Space Complexity S(n)S(n) refers to the amount of memory space required by the algorithm in relation to the input size nn.

•

Linear Search: A process that checks every element in a list sequentially until the target value is found or the list ends. Its worst-case complexity is O(n)O(n).

•

Binary Search: An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item. Its complexity is O(log⁡2n)O(\log_2 n).

•

Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Its complexity is O(n2)O(n^2) due to nested loops.

•

Big O Notation O(f(n))O(f(n)) is used to describe the upper bound of the execution time or space requirements of an algorithm.

📐Formulae

Maximum steps in Binary Search=⌈log⁡2n⌉\text{Maximum steps in Binary Search} = \lceil \log_2 n \rceil

Average comparisons in Linear Search=n+12\text{Average comparisons in Linear Search} = \frac{n + 1}{2}

Sum of first n integers (used in Sort analysis)=∑i=1ni=n(n+1)2\text{Sum of first } n \text{ integers (used in Sort analysis)} = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}

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

Efficiency Order: O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)\text{Efficiency Order: } O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)

💡Examples

Problem 1:

A sorted list contains n=64n = 64 elements. Determine the maximum number of comparisons required to find a specific element using Binary Search.

Solution:

In Binary Search, the maximum number of comparisons is given by the formula k=⌈log⁡2n⌉k = \lceil \log_2 n \rceil. Given n=64n = 64, we find kk such that 2k=642^k = 64. Since 26=642^6 = 64, we have: log⁡264=6\log_2 64 = 6 Therefore, the maximum number of comparisons is 66.

Explanation:

Binary search halves the search space in each step. Since 6464 can be divided by 22 exactly 66 times to reach 11, it takes 66 steps.

Problem 2:

Calculate the total number of comparisons made in a Bubble Sort algorithm for an array of 1010 elements in the worst-case scenario.

Solution:

The number of comparisons in Bubble Sort for nn elements is calculated as: Total Comparisons=n(n−1)2\text{Total Comparisons} = \frac{n(n-1)}{2} Substituting n=10n = 10: Total Comparisons=10×(10−1)2\text{Total Comparisons} = \frac{10 \times (10 - 1)}{2} Total Comparisons=10×92\text{Total Comparisons} = \frac{10 \times 9}{2} Total Comparisons=902=45\text{Total Comparisons} = \frac{90}{2} = 45

Explanation:

In the first pass, 99 comparisons are made; in the second, 88, and so on, until 11. The sum is 9+8+7+⋯+1=459 + 8 + 7 + \dots + 1 = 45.

Problem 3:

Compare the time complexity of two algorithms where Algorithm A takes TA(n)=100nT_A(n) = 100n steps and Algorithm B takes TB(n)=n2T_B(n) = n^2 steps. At what value of nn does Algorithm A become more efficient than Algorithm B?

Solution:

Algorithm A is more efficient than Algorithm B when TA(n)<TB(n)T_A(n) < T_B(n). 100n<n2100n < n^2 Dividing both sides by nn (assuming n>0n > 0): 100<n100 < n So, for all n>100n > 100, Algorithm A is more efficient.

Explanation:

Even though Algorithm A has a high constant factor (100100), its linear growth O(n)O(n) eventually becomes smaller than the quadratic growth O(n2)O(n^2) of Algorithm B as nn increases.