1. What is Time Complexity?

Time complexity tells us how the execution time of a program increases when the input size
increases.

It does not measure time in seconds.​

It measures the number of operations performed by the algorithm.

We express time complexity using Big-O notation.

2. Common Time Complexities (with Examples)

2.1 O(1) – Constant Time

The program takes the same time, no matter how large the input is.

Example:

int getFirst(int arr[]) {

return arr[0];
}

Explanation:

●​ Only one operation is performed.

●​ Input size does not matter.

Time Complexity = O(1)

2.2 O(n) – Linear Time

The execution time increases linearly with input size.

Example:

void printArray(int arr[], int n) {

for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
Explanation:

●​ Loop runs n times.

●​ If n doubles, time doubles.

Time Complexity = O(n)

2.3 O(n²) – Quadratic Time

Time increases very fast because of nested loops.

Example:

void printPairs(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("* ");
}
}
}

Explanation:

●​ Outer loop runs n times.

●​ Inner loop runs n times for each outer loop.
●​ Total operations = n × n.

Time Complexity = O(n²)

2.4 O(log n) – Logarithmic Time

The problem size is reduced by half in each step.

Example:

int binarySearch(int arr[], int n, int key) {

int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key)
 return mid;
else if(arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

Explanation:

●​ Search space reduces by half each time.

●​ Very efficient for large inputs.

Time Complexity = O(log n)

3. What is Space Complexity?

Space complexity tells us how much extra memory an algorithm uses apart from the input.

It includes:

●​ Variables
●​ Arrays
●​ Recursion stack

4. Common Space Complexities (with Examples)

4.1 O(1) – Constant Space

Uses a fixed amount of memory.

Example:

int sum(int a, int b) {

int result = a + b;
return result;
}

Explanation:
 ●​ Only one variable is used.
●​ Memory does not grow with input.

Space Complexity = O(1)

4.2 O(n) – Linear Space

Memory increases with input size.

Example:

void storeElements(int n) {
int arr[n];
}

Explanation:

●​ Array size depends on n.

Space Complexity = O(n)

4.3 O(n) – Recursion Stack Space

Each recursive call takes memory on the stack.

Example:

int factorial(int n) {
if(n == 0)
return 1;
return n * factorial(n - 1);
}

Explanation:

●​ For n, there are n function calls.

●​ Each call occupies memory.

Space Complexity = O(n)

5. Time vs Space Complexity (Quick Comparison)

Aspect Time Complexity Space Complexity

Measures Execution time Memory usage

Depends on Number of operations Extra memory

used

Important for Speed Memory efficiency

6. Key Points

●​ Loops affect time complexity

●​ Arrays and recursion affect space complexity
●​ Ignore constants (O(2n) = O(n))
●​ Nested loops usually mean O(n²)

Searching in Arrays

Definition

Searching in arrays refers to the process of finding the position (index) of a given element (key)
in an array. If the element is present, its index is returned; otherwise, the search reports that the
element is not found.

Types of Searching in Arrays

There are two commonly used searching techniques:

1.​ Linear Search

2.​ Binary Search

1. Linear Search

Linear search is the simplest searching technique. It checks each element of the array one by
one until the required element is found or the array ends.

This method works for both sorted and unsorted arrays.

Algorithm (Linear Search)

1.​ Start from the first element of the array.

2.​ Compare each element with the key.
3.​ If a match is found, return the index.
4.​ If the end of the array is reached, report that the element is not found.

Example

Array: {10, 25, 30, 45, 50}​

Key: 30

Comparisons:

10 ≠ 30
25 ≠ 30
30 = 30 → Found

Time Complexity

●​ Best Case: O(1) (element found at first position)

●​ Worst Case: O(n) (element at last position or not present)
●​ Average Case: O(n)

Space Complexity

●​ O(1)

Advantages

●​ Simple to understand and implement

●​ No requirement for sorted array

Disadvantages

●​ Inefficient for large datasets

2. Binary Search

Description

Binary search is an efficient searching technique that works on sorted arrays only. It repeatedly
divides the search space into half.

Algorithm (Binary Search)

1.​ Set low = 0 and high = n - 1.

2.​ Find mid = (low + high) / 2.
3.​ Compare array[mid] with the key:
○​ If equal, an element is found.
○​ If key < array[mid], search left half.
○​ If key > array[mid], search right half.
4.​ Repeat until the element is found or low > high.

Example

Sorted Array: {10, 20, 30, 40, 50}​

Key: 30

Steps:

mid = 2 → array[2] = 30 → Found

Time Complexity

●​ Best Case: O(1)

●​ Worst Case: O(log n)
●​ Average Case: O(log n)

Space Complexity

●​ Iterative: O(1)
●​ Recursive: O(log n) (due to recursion stack)

Advantages
 ●​ Very fast for large datasets
●​ Fewer comparisons

Disadvantages

●​ Works only on sorted arrays

●​ Slightly more complex than linear search

Comparison of Linear Search and Binary Search

Feature Linear Search Binary Search

Array Type Sorted / Sorted only

Unsorted

Time Complexity O(n) O(log n)

Simplicity Very simple Moderately complex

Efficiency Low High

1. Iterative Binary Search (C Program)

Program
#include <stdio.h>

int binarySearch(int arr[], int n, int key) {

int low = 0, high = n - 1, mid;

while (low <= high) {

mid = (low + high) / 2;

if (arr[mid] == key)
return mid;
else if (key < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int arr[50], n, key, i, result;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter elements in sorted order:\n");

for (i = 0; i < n; i++)
scanf("%d", &arr[i]);

printf("Enter element to search: ");

scanf("%d", &key);

result = binarySearch(arr, n, key);

if (result != -1)
printf("Element found at index %d", result);
else
printf("Element not found");

return 0;
}

2. Recursive Binary Search (C Program)

Program
#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {

int mid;

if (low <= high) {

mid = (low + high) / 2;

if (arr[mid] == key)
return mid;
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
 return -1;
}

int main() {
int arr[50], n, key, i, result;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter elements in sorted order:\n");

for (i = 0; i < n; i++)
scanf("%d", &arr[i]);

printf("Enter element to search: ");

scanf("%d", &key);

result = binarySearch(arr, 0, n - 1, key);

if (result != -1)
printf("Element found at index %d", result);
else
printf("Element not found");

return 0;
}

Key Notes

Binary search works only on sorted arrays

●​ Iterative binary search uses a loop and constant space

●​ Recursive binary search uses function calls and extra stack space

Time and Space Complexity

Method Time Complexity Space Complexity

Iterative O(log n) O(1)

 Recursiv O(log n) O(log n)
e

Bubble Sort

1. What is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm.​

It repeatedly compares adjacent elements and swaps them if they are in the wrong order.​
With each pass, the largest unsorted element “bubbles up” to its correct position at the end of
the array.

2. Key Idea

●​ Compare two neighboring elements

●​ Swap if the left element is greater than the right
●​ After one full pass, the largest element is placed at the end
●​ Repeat the process for the remaining unsorted part

3. Example for Understanding

Let the array be:

A = [5, 1, 4, 2, 8]
4. Dry Run (Step-by-Step)

Pass 1

Compare adjacent elements:

Comparison Result Array after step

5&1 Swap [1, 5, 4, 2, 8]

5&4 Swap [1, 4, 5, 2, 8]

5&2 Swap [1, 4, 2, 5, 8]

5&8 No [1, 4, 2, 5, 8]
swap

✔ Largest element 8 is now in correct position.

Pass 2

Comparison Result Array

1&4 No [1, 4, 2, 5, 8]
swap

4&2 Swap [1, 2, 4, 5, 8]

4&5 No [1, 2, 4, 5, 8]
swap

✔ Next largest element 5 is fixed.

Pass 3

Comparison Result Array

1&2 No [1, 2, 4, 5, 8]
swap
 2&4 No [1, 2, 4, 5, 8]
swap

✔ Array is sorted.

5. Algorithm (Steps)

1.​ Start from the first element

2.​ Compare adjacent elements
3.​ Swap if the left element is greater
4.​ Continue till the end of the array
5.​ Repeat for remaining elements
6.​ Stop when the array is sorted

6. Bubble Sort – C Program

#include <stdio.h>

int main() {
int arr[] = {5, 1, 4, 2, 8};
int n = 5;
int i, j, temp;

for (i = 0; i < n - 1; i++) {

for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

printf("Sorted array: ");

for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

7. Code Explanation

●​ Outer loop (i)​

Controls the number of passes​
After each pass, one element reaches its correct position
●​ Inner loop (j)​
Compares adjacent elements in the unsorted part
●​ Swap condition​
If arr[j] > arr[j+1], swap them
●​ n - i - 1​
Avoids comparing already sorted elements at the end

8. Time and Space Complexity

Case Time Complexity

Best Case (already O(n) (with optimization)

sorted)

Average Case O(n²)

Worst Case (reverse O(n²)

order)

Space Complexity: O(1) (in-place sorting)

9. Characteristics of Bubble Sort

●​ Simple and easy to understand

●​ Stable sorting algorithm
●​ Not efficient for large datasets
●​ Best suited for learning and small inputs

10. Summary
 ●​ Bubble Sort repeatedly swaps adjacent elements
●​ Largest element moves to the end in each pass
●​ Uses nested loops
●​ Time complexity is O(n²)
●​ Easy but inefficient for large data

Selection Sort

1. What is Selection Sort?

Selection Sort is a comparison-based sorting algorithm that works by repeatedly selecting the
smallest element from the unsorted portion of the array and placing it at the beginning.

Unlike Bubble Sort, Selection Sort makes minimum swaps.

2. Key Idea

●​ Divide the array into sorted and unsorted parts

●​ Initially, the sorted part is empty
●​ Find the minimum element in the unsorted part
●​ Swap it with the first element of the unsorted part
●​ Move the boundary of the sorted part one step forward

3. Example for Understanding

Let the array be:

A = [64, 25, 12, 22, 11]

4. Dry Run (Step-by-Step)

Pass 1

Unsorted part: [64, 25, 12, 22, 11]​

Minimum element = 11
Swap 64 and 11:

[11, 25, 12, 22, 64]

✔ First element is now sorted

Pass 2

Unsorted part: [25, 12, 22, 64]​

Minimum element = 12

Swap 25 and 12:

[11, 12, 25, 22, 64]

✔ First two elements are sorted

Pass 3

Unsorted part: [25, 22, 64]​

Minimum element = 22

Swap 25 and 22:

[11, 12, 22, 25, 64]

Pass 4

Unsorted part: [25, 64]​

Minimum element = 25

No swap required

✔ Array is sorted

5. Algorithm (Steps)
 1.​ Start from index 0
2.​ Assume the first unsorted element is the minimum
3.​ Compare it with the remaining elements
4.​ If a smaller element is found, update the minimum index
5.​ Swap the minimum element with the first unsorted element
6.​ Repeat for the remaining array

6. Selection Sort – C Program

#include <stdio.h>

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = 5;
int i, j, minIndex, temp;

for (i = 0; i < n - 1; i++) {

minIndex = i;

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum element

temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}

printf("Sorted array: ");

for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

7. Code Explanation
 ●​ Outer loop (i)​
Marks the beginning of the unsorted part
●​ minIndex​
Stores the index of the smallest element
●​ Inner loop (j)​
Searches for the minimum element in the unsorted part
●​ Swap operation​
Places the smallest element at its correct position

8. Time and Space Complexity

Case Time Complexity

Best Case O(n²)

Average O(n²)
Case

Worst Case O(n²)

Space Complexity: O(1) (In-place)

9. Characteristics of Selection Sort

●​ Simple and easy to implement

●​ Performs fewer swaps than Bubble Sort
●​ Not a stable sorting algorithm (in general form)
●​ Inefficient for large datasets

10. Bubble Sort vs Selection Sort

Feature Bubble Sort Selection Sort

Swaps Many Very few

Comparison Many Many

s

Stability Stable Not stable

 Efficiency Low Low

11. Summary (For Exams)

●​ Selection Sort selects the minimum element

●​ Sorted and unsorted sections are maintained
●​ Time complexity is O(n²)
●​ Suitable for small datasets and learning

Below is a complete, exam-ready explanation of Insertion Sort, written clearly for DSA / C
programming students.

Insertion Sort

Definition

Insertion sort is a comparison-based sorting algorithm that sorts an array by taking one element
at a time and inserting it into its correct position in the already sorted part of the array.

It works in a way similar to arranging playing cards in hand.

Working Principle

●​ The array is divided into two parts:

○​ Sorted part (left side)
○​ Unsorted part (right side)
●​ Initially, the first element is considered sorted.
●​ Each next element is picked and placed at the correct position in the sorted part by
shifting elements.

Algorithm (Insertion Sort)

1.​ Start from the second element of the array (index 1).
2.​ Store the current element as key.
3.​ Compare key with elements before it.
 4.​ Shift all elements greater than key one position to the right.
5.​ Insert key at its correct position.
6.​ Repeat until the array is sorted.

C Program for Insertion Sort

#include <stdio.h>

int main() {

int arr[50], n, i, j, key;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter array elements:\n");

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j--;

}
 arr[j + 1] = key;

printf("Sorted array:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

return 0;

Dry Run

Input

Array = {8, 3, 5, 2}

Pass 1 (i = 1, key = 3)

8 > 3 → shift 8

Insert 3

Array: {3, 8, 5, 2}

Pass 2 (i = 2, key = 5)

8 > 5 → shift 8

Insert 5

Array: {3, 5, 8, 2}
Pass 3 (i = 3, key = 2)

8 > 2 → shift

5 > 2 → shift

3 > 2 → shift

Insert 2

Array: {2, 3, 5, 8}

Given Array

{4, 3, 5, 2, 1}

Insertion sort starts from index 1 because the first element is assumed to be already sorted.

Initial State

Sorted part: {4}

Unsorted part: {3, 5, 2, 1}

Pass 1 (i = 1)

Key = 3​
Compare with elements to the left.

4 > 3 → shift 4 to the right

Insert 3 at index 0
Array after Pass 1

{3, 4, 5, 2, 1}

Pass 2 (i = 2)

Key = 5​
Compare with elements to the left.

4 < 5 → no shift needed

Array after Pass 2

{3, 4, 5, 2, 1}

Pass 3 (i = 3)

Key = 2​
Compare with elements to the left.

5 > 2 → shift 5

4 > 2 → shift 4

3 > 2 → shift 3

Insert 2 at index 0

Array after Pass 3

{2, 3, 4, 5, 1}
Pass 4 (i = 4)

Key = 1​
Compare with elements to the left.

5 > 1 → shift 5

4 > 1 → shift 4

3 > 1 → shift 3

2 > 1 → shift 2

Insert 1 at index 0

Array after Pass 4

{1, 2, 3, 4, 5}

Final Sorted Array

{1, 2, 3, 4, 5}

Quick Pass

Pas Key Array State

s

1 3 {3, 4, 5, 2, 1}
2 5 {3, 4, 5, 2, 1}

3 2 {2, 3, 4, 5, 1}

4 1 {1, 2, 3, 4, 5}

Key Observation

●​ Maximum shifting happens in Pass 3 and Pass 4

●​ This input is close to the worst case
●​ Time Complexity here approaches O(n²)

Time Complexity

Case Time Complexity

Best Case (Already sorted) O(n)

Average Case O(n²)

Worst Case (Reverse O(n²)

order)

Space Complexity

●​ O(1) (In-place sorting)

Advantages

●​ Simple and easy to implement

●​ Efficient for small datasets
●​ Stable sorting algorithm
●​ Adaptive (fast for nearly sorted arrays)

Disadvantages

●​ Inefficient for large datasets

●​ Slower compared to algorithms like Merge Sort or Quick Sort

Real-World Example

Sorting playing cards in hand:

●​ Pick one card at a time

●​ Insert it in the correct position among already sorted cards

Insertion sort sorts elements by repeatedly inserting each element into its correct position in the
sorted part of the array.