krit.club logo

The World of Algorithms - Analysing these Algorithms

Grade 9CBSE

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

🔑Concepts

•

An algorithm is a well-defined, step-by-step procedure to solve a specific problem in a finite number of steps.

•

Characteristics of a good algorithm include Finiteness, Definiteness (clear steps), Input, Output, and Effectiveness.

•

Analysing an algorithm involves measuring its efficiency in terms of Time Complexity T(n)T(n) and Space Complexity S(n)S(n), where nn is the input size.

•

Time complexity represents the amount of time an algorithm takes to run, usually expressed using Big O notation O(f(n))O(f(n)).

•

Linear Search is an algorithm that checks every element in a list one by one until the target is found. Its worst-case time complexity is O(n)O(n).

•

Binary Search is a more efficient algorithm used on sorted lists. It repeatedly divides the search interval in half. Its worst-case time complexity is O(log⁡2n)O(\log_2 n).

•

Comparison of efficiency: For large values of nn, an algorithm with complexity O(log⁡n)O(\log n) is significantly faster than one with O(n)O(n), and O(n)O(n) is faster than O(n2)O(n^2).

📐Formulae

T(n)=O(f(n))T(n) = O(f(n))

Max comparisons in Linear Search=n\text{Max comparisons in Linear Search} = n

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

Sum of first n natural numbers=n(n+1)2\text{Sum of first } n \text{ natural numbers} = \frac{n(n + 1)}{2}

💡Examples

Problem 1:

Compare the number of comparisons required to find a number in a sorted list of 10241024 elements using Linear Search and Binary Search in the worst-case scenario.

Solution:

  1. For Linear Search: In the worst case, the algorithm searches all nn elements. Number of comparisons = n=1024n = 1024.

  2. For Binary Search: In the worst case, the number of comparisons is log⁡2n\log_2 n. Since 210=10242^{10} = 1024, then log⁡21024=10\log_2 1024 = 10. Number of comparisons = 1010.

Explanation:

Linear Search grows linearly with input size, while Binary Search grows logarithmically, making it much faster for large sorted datasets.

Problem 2:

An algorithm calculates the sum of the first nn numbers using a loop that iterates nn times. Another algorithm uses the formula n(n+1)2\frac{n(n+1)}{2}. Identify their time complexities.

Solution:

  1. Loop Algorithm: Since the loop runs from 11 to nn, the number of operations is proportional to nn. Time Complexity = O(n)O(n).

  2. Formula Algorithm: The formula involves a fixed number of operations (one addition, one multiplication, and one division) regardless of the value of nn. Time Complexity = O(1)O(1) (Constant time).

Explanation:

The formula-based approach is more efficient because its execution time does not increase with the size of the input nn.