Login
OR
Don't worry. We'll fix this for you!
Imagine you want to bake a cake. You follow a recipe - a clear set of instructions that tells you what ingredients to use, how to mix them, and how long to bake. In computer science, an algorithm is like that recipe: a step-by-step procedure to solve a problem or perform a task.
Algorithms are the heart of programming and computer applications. Every program you use, from simple calculators to complex banking software, runs on algorithms. Understanding algorithms helps you think logically, solve problems efficiently, and write better code.
In this chapter, we will explore what algorithms are, how to design them, how to represent them visually, and how to analyze their efficiency. We will also look at common types of algorithms and solve examples to build your confidence.
An algorithm is a finite sequence of well-defined instructions, typically used to solve a class of problems or perform a computation.
To be considered a valid algorithm, it must have certain key properties. These properties ensure that the algorithm is clear, effective, and useful.
| Property | Definition | Example |
|---|---|---|
| Finiteness | The algorithm must always terminate after a finite number of steps. | Recipe to bake a cake finishes after mixing and baking, not infinite steps. |
| Definiteness | Each step must be precisely defined and unambiguous. | "Add 2 cups of flour" is clear; "Add some flour" is not. |
| Input | Zero or more inputs are taken before or during execution. | Input numbers to find their sum. |
| Output | At least one output is produced as a result of the algorithm. | Sum of input numbers displayed. |
| Effectiveness | All operations must be basic enough to be performed exactly and in finite time. | Simple arithmetic operations like addition or comparison. |
These properties ensure that an algorithm is not just a vague idea but a concrete, executable plan.
Once you understand what an algorithm is, the next step is to represent it clearly. Two common methods are pseudocode and flowcharts.
Pseudocode is a way to write down the steps of an algorithm using simple, plain language that resembles programming but is not tied to any specific language syntax. It helps you focus on the logic without worrying about details like punctuation or keywords.
For example, to find the maximum of two numbers, pseudocode might look like this:
STARTInput number1, number2IF number1 > number2 THEN max = number1ELSE max = number2END IFOutput maxSTOP
A flowchart is a visual diagram that shows the flow of control in an algorithm using symbols like arrows, rectangles, diamonds, and ovals. It helps you visualize the sequence of steps and decisions.
Here is a flowchart for finding the maximum of two numbers:
graph TD A[Start] --> B[Input number1, number2] B --> C{Is number1 > number2?} C -- Yes --> D[Set max = number1] C -- No --> E[Set max = number2] D --> F[Output max] E --> F F --> G[Stop]This flowchart clearly shows the decision-making process and the flow of the algorithm.
Sorting is a common task in programming: arranging data in a specific order, like ascending or descending. Several algorithms exist for sorting, each with different approaches and efficiencies.
Bubble Sort is the simplest sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.
Imagine bubbles rising in water - the largest element "bubbles up" to the end in each pass.
Here is a flowchart illustrating the Bubble Sort process on a small array:
graph TD A[Start] --> B[Set i = 0] B --> C{Is i < n-1?} C -- No --> J[Stop] C -- Yes --> D[Set j = 0] D --> E{Is j < n-i-1?} E -- No --> I[Increment i by 1] E -- Yes --> F{Is arr[j] > arr[j+1]?} F -- Yes --> G[Swap arr[j] and arr[j+1]] F -- No --> H[Increment j by 1] G --> H H --> E I --> CBubble Sort is easy to understand but inefficient for large datasets. We will explore other sorting algorithms later.
Not all algorithms are equally efficient. Some solve problems quickly, while others take a long time or use a lot of memory. To compare algorithms, we analyze their time complexity and space complexity.
Time complexity measures how the running time of an algorithm increases with the size of the input (usually denoted as \( n \)). For example, if an algorithm takes 1 second for 10 inputs and 4 seconds for 20 inputs, its time complexity grows faster than linear.
Space complexity measures how much extra memory an algorithm uses as input size grows.
Big O notation is a mathematical way to describe the upper bound of an algorithm's growth rate. It tells us how the running time or space requirement grows relative to input size \( n \), ignoring constants and lower-order terms.
| Algorithm | Time Complexity (Worst Case) | Explanation |
|---|---|---|
| Bubble Sort | O(n2) | Compares each pair, nested loops cause quadratic growth. |
| Selection Sort | O(n2) | Finds minimum repeatedly, similar nested loops. |
| Insertion Sort | O(n2) | Inserts elements into sorted part, quadratic in worst case. |
| Binary Search | O(log n) | Divides search space in half each step, very efficient. |
| Linear Search | O(n) | Checks each element one by one. |
Understanding these complexities helps you choose the right algorithm for your problem.
Step 1: Input the three numbers: num1, num2, num3.
Step 2: Compare num1 and num2.
Step 3: Let max = greater of num1 and num2.
Step 4: Compare max with num3.
Step 5: If num3 > max, then max = num3.
Step 6: Output max as the largest number.
Answer: The algorithm correctly identifies the maximum of three numbers.
Flowchart for this algorithm:
graph TD A[Start] --> B[Input num1, num2, num3] B --> C{Is num1 > num2?} C -- Yes --> D[Set max = num1] C -- No --> E[Set max = num2] D --> F{Is num3 > max?} E --> F F -- Yes --> G[Set max = num3] F -- No --> H[Do nothing] G --> I[Output max] H --> I I --> J[Stop]Step 1: Compare 5 and 3, since 5 > 3, swap. Array: [3, 5, 8, 4, 2]
Step 2: Compare 5 and 8, no swap. Array remains [3, 5, 8, 4, 2]
Step 3: Compare 8 and 4, swap. Array: [3, 5, 4, 8, 2]
Step 4: Compare 8 and 2, swap. Array: [3, 5, 4, 2, 8]
Step 5: First pass complete, largest element 8 is at the end.
Step 6: Repeat passes for remaining elements:
Final sorted array: [2, 3, 4, 5, 8]
Step 1: Set low = 0, high = 6 (array indices).
Step 2: Calculate mid = (low + high) / 2 = 3.
Step 3: Check element at mid: arr[3] = 8.
Step 4: Since 10 > 8, set low = mid + 1 = 4.
Step 5: Calculate new mid = (4 + 6) / 2 = 5.
Step 6: Check arr[5] = 12.
Step 7: Since 10 < 12, set high = mid - 1 = 4.
Step 8: Calculate mid = (4 + 4) / 2 = 4.
Step 9: Check arr[4] = 10, found the element.
Answer: Element 10 is present at index 4.
for i = 1 to n for j = 1 to n print(i, j)
Step 1: Outer loop runs from 1 to n, so it executes n times.
Step 2: For each iteration of the outer loop, inner loop runs n times.
Step 3: Total operations = n (outer) x n (inner) = \( n^2 \).
Step 4: Each print statement is a constant time operation.
Answer: Time complexity is \( O(n^2) \), quadratic time.
Step 1: Fibonacci series: 0, 1, 1, 2, 3, 5, 8, ... where each number is sum of previous two.
Step 2: Recursive method recalculates values multiple times, inefficient.
Step 3: Use dynamic programming to store computed Fibonacci numbers in an array.
Step 4: Initialize fib[0] = 0, fib[1] = 1.
Step 5: For i = 2 to 10, compute fib[i] = fib[i-1] + fib[i-2].
Step 6: fib[2] = 1, fib[3] = 2, ..., fib[10] = 55.
Answer: The 10th Fibonacci number is 55.
When to use: When beginning any algorithm design or problem-solving task.
When to use: When the algorithm has multiple decision points or loops.
When to use: During exam time to evaluate and compare algorithms.
When to use: When solving sorting-related questions in exams.
When to use: Before implementing algorithms in any programming language.
Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.
Go to practice →
Your Score
Your Rank
| Rank | Name | Score |
|---|