📘 Module 4: Recursion (5 Lectures)

🎓 Module 4: Recursion

Total Lectures: 5

📖 Lecture 1: Introduction to Recursion

🔹 What is Recursion?

Recursion is a programming technique in which a function calls itself to solve a problem.

Instead of using loops (for, while), recursion repeatedly breaks a problem into smaller subproblems until a stopping condition (called the Base Case) is reached.

</div>

🎯 Real-Life Examples

📂 Opening a folder inside another folder.

🪞 Looking into two mirrors facing each other.

🪆 Russian Dolls (Matryoshka Dolls)

🏢 Climbing stairs one step at a time.

General Syntax


return_type function_name(parameters)
{
    if(base_condition)
        return value;

    return function_name(smaller_problem);
}

Basic Structure of Recursion


            Function Call
                  │
          Is Base Case True?
             /           \
          Yes             No
          │               │
 Return Result      Call Same Function
                        │
                  Smaller Problem

Important Terms

Term	Meaning
Recursive Function	Function that calls itself
Base Case	Stops recursion
Recursive Call	Function calling itself
Call Stack	Stores function calls

Example 1: Print Numbers from 1 to 5


#include<stdio.h>

void print(int n)
{
    if(n>5)
        return;

    printf("%d ",n);

    print(n+1);
}

int main()
{
    print(1);
    return 0;
}

Output


1 2 3 4 5

Example 2: Countdown


#include<stdio.h>

void countdown(int n)
{
    if(n==0)
        return;

    printf("%d ",n);

    countdown(n-1);
}

int main()
{
    countdown(5);
}

Output


5 4 3 2 1

📖 Lecture 2: Developing Recursive Definition of Simple Problems

Steps to Develop Recursive Solution

Step 1

Identify the smallest problem.

Step 2

Find the Base Case.

Step 3

Reduce the problem.

Step 4

Call the function again.

</div>

Example 1: Factorial

Mathematical Definition


5! = 5×4×3×2×1

n! = n × (n-1)!

0! = 1

Algorithm


factorial(n)

if n==0
    return 1

return n * factorial(n-1)

Program


#include<stdio.h>

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

    return n*factorial(n-1);
}

int main()
{
    printf("%d",factorial(5));
}

Output

Example 2: Sum of First N Numbers


Sum(5)

5+4+3+2+1

=5+Sum(4)

Program


#include<stdio.h>

int sum(int n)
{
    if(n==0)
        return 0;

    return n+sum(n-1);
}

int main()
{
    printf("%d",sum(5));
}

Output

Example 3: Power


2^5

=2 × Power(2,4)

Program


#include<stdio.h>

int power(int a,int b)
{
    if(b==0)
        return 1;

    return a*power(a,b-1);
}

int main()
{
    printf("%d",power(2,5));
}

Output

📖 Lecture 3: Advantages and Limitations of Recursion

🌟 Advantages

✔ Simple Code

✔ Easy to Understand

✔ Less Coding

✔ Suitable for Tree Problems

✔ Useful in Graph Algorithms

✔ Natural Solution for Divide & Conquer

✔ Cleaner than loops in many algorithms

</div>

Applications

Application	Example
Tree Traversal	Inorder, Preorder
Graph Search	DFS
Sorting	Merge Sort
Searching	Binary Search
Mathematics	Factorial
Dynamic Programming	Memoization
Compiler	Parsing

⚠ Limitations

❌ More Memory

❌ Function Call Overhead

❌ Slower than Loops

❌ Stack Overflow

❌ Difficult Debugging

❌ Infinite Recursion if Base Case Missing

</div>

Comparison

Feature	Iteration	Recursion
Uses Loop	Yes	No
Uses Stack	No	Yes
Speed	Faster	Slower
Memory	Less	More
Code	Longer	Shorter
Debugging	Easy	Difficult

📖 Lecture 4: Understanding Internal Stack Implementation

Every Recursive Call Creates

✔ Parameters

✔ Local Variables

✔ Return Address

✔ Function State

All are stored inside the Call Stack.

Example


factorial(4)

Calls


factorial(4)

↓

factorial(3)

↓

factorial(2)

↓

factorial(1)

↓

factorial(0)

Stack Formation


Top

factorial(0)

factorial(1)

factorial(2)

factorial(3)

factorial(4)

Bottom

Returning Phase


factorial(0)=1

↓

factorial(1)=1×1

↓

factorial(2)=2×1

↓

factorial(3)=3×2

↓

factorial(4)=4×6=24

Visual Diagram


CALLS

main()

↓

fact(4)

↓

fact(3)

↓

fact(2)

↓

fact(1)

↓

fact(0)

-------------------

RETURNS

1

↓

1

↓

2

↓

6

↓

24

Stack Memory Illustration


+--------------------+
| factorial(0) |
+--------------------+
| factorial(1) |
+--------------------+
| factorial(2) |
+--------------------+
| factorial(3) |
+--------------------+
| factorial(4) |
+--------------------+
| main() |
+--------------------+

📖 Lecture 5: Programs Using Recursion

Program 1: Fibonacci Series


#include<stdio.h>

int fib(int n)
{
    if(n<=1)
        return n;

    return fib(n-1)+fib(n-2);
}

int main()
{
    int i;

    for(i=0;i<10;i++)
        printf("%d ",fib(i));
}

Output


0 1 1 2 3 5 8 13 21 34

Program 2: Reverse a Number


#include<stdio.h>

void reverse(int n)
{
    if(n==0)
        return;

    printf("%d",n%10);

    reverse(n/10);
}

int main()
{
    reverse(12345);
}

Output

Program 3: Print Array


#include<stdio.h>

void display(int a[],int n,int i)
{
    if(i==n)
        return;

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

    display(a,n,i+1);
}

int main()
{
    int a[]={10,20,30,40};

    display(a,4,0);
}

Output


10 20 30 40

Program 4: GCD Using Recursion


#include<stdio.h>

int gcd(int a,int b)
{
    if(b==0)
        return a;

    return gcd(b,a%b);
}

int main()
{
    printf("%d",gcd(18,12));
}

Output

Program 5: Decimal to Binary


#include<stdio.h>

void binary(int n)
{
    if(n==0)
        return;

    binary(n/2);

    printf("%d",n%2);
}

int main()
{
    binary(13);
}

Output

🎯 Viva Questions

Define recursion.
What is a recursive function?
What is the base case?
Why is the base case necessary?
Explain the recursive case.
What is a call stack?
Why can recursion cause stack overflow?
Differentiate recursion and iteration.
Give real-life examples of recursion.
Explain internal stack implementation with an example.

📌 Interview Questions

Can every recursive program be converted into an iterative program?
Why is recursion slower than iteration?
What is tail recursion?
What is indirect recursion?
How does the compiler manage recursive function calls?
What happens if the base case is omitted?
Which data structure is used internally to implement recursion?

📘 Tail Recursion

🔹 Definition

Tail Recursion is a type of recursion in which the recursive function call is the last statement executed in the function. After the recursive call, no further computation or operation is performed.

In simple words: A function is tail recursive if it immediately returns the result of its recursive call.

🔑 Characteristics of Tail Recursion

✅ The recursive call is the last operation in the function.
✅ No calculation is performed after the recursive call.
✅ Easier for some compilers to optimize (called Tail Call Optimization, although many C compilers do not always apply it).
✅ Generally more memory-efficient when optimized.

📊 General Syntax


return_type function_name(parameters)
{
    if (base_condition)
        return value;

    return function_name(smaller_problem);   // Last statement
}

Example 1: Print Numbers from 1 to 5


#include <stdio.h>

void print(int n)
{
    if (n > 5)
        return;

    printf("%d ", n);

    print(n + 1);      // Last statement
}

int main()
{
    print(1);
    return 0;
}

Output


1 2 3 4 5

Explanation

print(1) prints 1
Calls print(2)
print(2) prints 2
Continues until print(5)
Finally reaches the base case when n > 5

Since nothing executes after print(n + 1), this is Tail Recursion.

Example 2: Countdown


#include <stdio.h>

void countdown(int n)
{
    if (n == 0)
        return;

    printf("%d ", n);

    countdown(n - 1);
}

int main()
{
    countdown(5);
}

Output


5 4 3 2 1

Again, the recursive call is the last statement, so this is Tail Recursion.

Tail Recursive Factorial

A normal factorial function is not tail recursive because multiplication happens after the recursive call.

Tail Recursive Version


#include <stdio.h>

int factorial(int n, int result)
{
    if (n == 0)
        return result;

    return factorial(n - 1, n * result);
}

int main()
{
    printf("%d", factorial(5, 1));
    return 0;
}

Output

How It Works

Function Call	Result
factorial(5,1)	factorial(4,5)
factorial(4,5)	factorial(3,20)
factorial(3,20)	factorial(2,60)
factorial(2,60)	factorial(1,120)
factorial(1,120)	factorial(0,120)
factorial(0,120)	120

Memory Flow


main()
   │
factorial(5,1)
   │
factorial(4,5)
   │
factorial(3,20)
   │
factorial(2,60)
   │
factorial(1,120)
   │
factorial(0,120)
   │
Return 120

Tail Recursion vs Non-Tail Recursion

Feature	Tail Recursion	Non-Tail Recursion
Recursive call	Last statement	Followed by more operations
Work after recursive call	No	Yes
Compiler optimization	Possible	Usually not possible
Memory usage	Can be lower if optimized	Usually higher

Tail Recursion Example


return factorial(n - 1, n * result);

No work remains after the recursive call.

Non-Tail Recursion Example


return n * factorial(n - 1);

Multiplication occurs after the recursive call returns, so it is not tail recursion.

Advantages

✔ Cleaner recursive logic.
✔ Can be optimized by some compilers.
✔ May reduce stack usage when optimized.
✔ Suitable for large recursive computations (if optimization is available).

Limitations

❌ Not every recursive problem can be written as tail recursion.
❌ Some C compilers do not perform tail call optimization.
❌ Often requires extra parameters (accumulators), making the function slightly more complex.

📘 How to Remove Tail Recursion (Convert Tail Recursion to Iteration)

Removing tail recursion means converting a tail recursive function into an iterative (loop-based) function. Since the recursive call is the last operation, it can be easily replaced with a loop.

Steps to Remove Tail Recursion

Remove the recursive function call.
Replace it with a loop (while or for).
Update the function parameters inside the loop.
Stop the loop when the base condition is reached.

Example 1: Tail Recursive Countdown

Tail Recursive Program


#include <stdio.h>

void countdown(int n)
{
    if (n == 0)
        return;

    printf("%d ", n);

    countdown(n - 1);
}

int main()
{
    countdown(5);
    return 0;
}

Output


5 4 3 2 1

After Removing Tail Recursion (Using `while` Loop)


#include <stdio.h>

void countdown(int n)
{
    while (n > 0)
    {
        printf("%d ", n);
        n--;
    }
}

int main()
{
    countdown(5);
    return 0;
}

Output


5 4 3 2 1

Example 2: Print Numbers from 1 to 5

Tail Recursive Version


#include <stdio.h>

void print(int n)
{
    if (n > 5)
        return;

    printf("%d ", n);

    print(n + 1);
}

int main()
{
    print(1);
}

Iterative Version


#include <stdio.h>

void print(int n)
{
    while (n <= 5)
    {
        printf("%d ", n);
        n++;
    }
}

int main()
{
    print(1);
}

Example 3: Tail Recursive Factorial

Tail Recursive Version


#include <stdio.h>

int fact(int n, int result)
{
    if (n == 0)
        return result;

    return fact(n - 1, n * result);
}

int main()
{
    printf("%d", fact(5, 1));
}

Iterative Version


#include <stdio.h>

int fact(int n)
{
    int result = 1;

    while (n > 0)
    {
        result = result * n;
        n--;
    }

    return result;
}

int main()
{
    printf("%d", fact(5));
}

Output

General Method

Tail Recursive Function


function(parameter)
{
    if(base condition)
        return;

    // Process

    function(updated parameter);
}

⬇️ Convert into

Iterative Function


function(parameter)
{
    while(base condition is false)
    {
        // Process

        Update parameter;
    }
}

Why Remove Tail Recursion?

✅ Avoids recursive function calls.
✅ Reduces memory usage (no call stack needed).
✅ Prevents stack overflow.
✅ Often improves performance.

Comparison

Tail Recursion	Iteration
Uses function calls	Uses loops
Uses call stack	No call stack
May consume more memory	Uses less memory
Easier to write for recursive problems	Often faster

Viva Questions

What is tail recursion?
Why can tail recursion be converted into iteration?
Which loop is commonly used to remove tail recursion?
What are the advantages of removing tail recursion?
Does removing tail recursion change the output of the program?

📘 Module 6: Searching, Sorting and Hashing

📖 Lecture 1: Searching and Linear Search

🎯 Learning Objectives

After completing this lecture, students will be able to:

Understand the concept of searching.
Explain Linear Search.
Write the Linear Search algorithm.
Implement Linear Search in C.
Analyze its time complexity.
Identify its advantages and disadvantages.

🔍 What is Searching?

Searching is the process of finding a specific element (key) in a collection of data such as an array, list, or database.

If the element is found, its position (index) is returned. Otherwise, the search reports that the element is not present.

</div>

🌍 Real-Life Examples

📞 Searching a contact in a phone book.
📚 Finding a book in a library.
🎓 Searching a student's roll number.
💻 Searching a file on a computer.
🛒 Finding a product on an e-commerce website.

Types of Searching


Searching
│
├── Linear Search
│
└── Binary Search

What is Linear Search?

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

</div>

Characteristics

Simple to understand and implement.
Searches sequentially.
Works with both sorted and unsorted arrays.
No preprocessing is required.

Algorithm for Linear Search


Step 1: Start

Step 2: Read the array, size (n), and key.

Step 3: Set i = 0.

Step 4: Compare key with A[i].

Step 5:
If A[i] == key
      Display "Element Found"
      Stop

Step 6:
Otherwise increment i.

Step 7:
Repeat until i = n.

Step 8:
If not found
Display "Element Not Found"

Step 9: Stop

Flowchart


            Start
              │
              ▼
      Read Array & Key
              │
              ▼
           i = 0
              │
              ▼
        Is i < n ?
          /      \
        No        Yes
        │          │
        ▼          ▼
 Not Found   Is A[i]==Key ?
                 /      \
              Yes        No
              │          │
              ▼          ▼
      Element Found     i++
              │          │
              └──────────┘
                     │
                     ▼
                    End

C Program


#include <stdio.h>

int main()
{
    int a[100], n, key, i, found = 0;

    printf("Enter number of elements: ");
    scanf("%d", &n);

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

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

    printf("Enter element to search: ");
    scanf("%d", &key);

    for(i = 0; i < n; i++)
    {
        if(a[i] == key)
        {
            found = 1;
            break;
        }
    }

    if(found)
        printf("Element found at position %d", i + 1);
    else
        printf("Element not found");

    return 0;
}

Sample Input


Enter number of elements: 5

10 25 40 18 90

Enter element to search: 40

Output


Element found at position 3

Dry Run

Array:


Index : 0   1   2   3   4

Value :10  25  40  18  90

Searching for 40

Step	Compared Value	Result
1	10	Not Found
2	25	Not Found
3	40	Found ✅

Time Complexity

Case	Complexity
Best Case	O(1)
Average Case	O(n)
Worst Case	O(n)

Space Complexity


O(1)

Only one extra variable is used.

Advantages

✔ Very easy to implement.
✔ Works on both sorted and unsorted arrays.
✔ No additional memory required.
✔ Suitable for small datasets.

</div>

Disadvantages

✘ Slow for large datasets.
✘ May require checking every element.
✘ Less efficient than Binary Search on sorted data.

</div>

Applications

Searching in small arrays.
Student record lookup.
Employee database.
Product search in a small inventory.
Contact list search.

Comparison of Search Success

Suppose the array is:


5  8  10  15  20  25

Searching for 20


5 ❌

8 ❌

10 ❌

15 ❌

20 ✅ Found

Viva Questions

What is searching?
Define Linear Search.
Does Linear Search require a sorted array?
What is the best-case time complexity of Linear Search?
What is the worst-case time complexity?
What is the space complexity of Linear Search?
Name two applications of Linear Search.

MCQs

1. Linear Search works on:

A. Only sorted arrays
B. Only linked lists
✅ C. Both sorted and unsorted arrays
D. Only trees

2. Worst-case complexity of Linear Search is:

A. O(1)
B. O(log n)
✅ C. O(n)
D. O(n²)

3. Which search checks elements one by one?

A. Binary Search
✅ B. Linear Search
C. Hash Search
D. DFS

University Exam Questions

Short Questions

Define Linear Search.
Write the algorithm of Linear Search.
State the advantages and disadvantages of Linear Search.

Long Questions

Explain Linear Search with an algorithm and C program.
Discuss the time complexity of Linear Search.
Explain the working of Linear Search with an example.

Quick Revision

Topic	Key Point
Searching	Finding a specific element
Linear Search	Sequential search
Works On	Sorted and Unsorted Arrays
Best Case	O(1)
Worst Case	O(n)
Space Complexity	O(1)

📌 Key Takeaways

Linear Search examines each element one by one until the target is found or the array ends.
It is simple to implement and does not require the data to be sorted.
It is suitable for small datasets, but becomes inefficient for large datasets because its worst-case time complexity is O(n).

Lecture 2: Binary Search (BCA Notes)

🎯 Learning Objectives

After completing this lecture, students will be able to:

Define Binary Search.
Understand the working principle of Binary Search.
Write the Binary Search algorithm.
Implement Binary Search in C (Iterative and Recursive).
Analyze the time complexity.
Compare Binary Search with Linear Search.

🔍 What is Binary Search?

Binary Search is an efficient searching algorithm that works only on a sorted array. It repeatedly divides the search interval into two equal halves until the required element is found or the search interval becomes empty.

</div>

🌟 Key Idea

Instead of checking every element one by one, Binary Search compares the target element with the middle element.

If the key is equal to the middle element → Found
If the key is smaller → Search the left half
If the key is larger → Search the right half

📌 Prerequisite

The array must be sorted (ascending or descending order).

Example (Ascending Order):


Index : 0   1   2   3   4   5   6

Value :10  20  30  40  50  60  70

Working Principle

Suppose we want to search 50.

Step 1


10   20   30   40   50   60   70
                ↑
             Middle = 40

Since 50 > 40, search the right half.

Step 2


50   60   70
     ↑
Middle = 60

Since 50 < 60, search the left half.

Step 3


50
↑
Found

Algorithm (Iterative)


Step 1 : Start

Step 2 : Read the sorted array, size n, and key.

Step 3 : low = 0
         high = n - 1

Step 4 : Repeat while low <= high

Step 5 : mid = (low + high) / 2

Step 6 :
If key == A[mid]
      Display "Found"
      Stop

Step 7 :
If key < A[mid]
      high = mid - 1

Otherwise
      low = mid + 1

Step 8 :
Repeat

Step 9 :
Display "Not Found"

Step 10 : Stop

Flowchart


             Start
               │
               ▼
     Read Sorted Array & Key
               │
               ▼
      low=0, high=n-1
               │
               ▼
         low <= high ?
          /          \
        No            Yes
        │              │
        ▼              ▼
 Not Found     mid=(low+high)/2
                      │
                      ▼
                key==A[mid]?
                 /        \
              Yes          No
              │             │
              ▼             ▼
          Element      key < A[mid] ?
           Found         /        \
                        Yes        No
                        │          │
                        ▼          ▼
                  high=mid-1   low=mid+1
                         │
                         └───────────────┐
                                         │
                                         ▼
                                    Repeat

C Program (Iterative Binary Search)


#include <stdio.h>

int main()
{
    int a[100], n, key;
    int low, high, mid, i;

    printf("Enter number of elements: ");
    scanf("%d",&n);

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

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

    printf("Enter element to search: ");
    scanf("%d",&key);

    low=0;
    high=n-1;

    while(low<=high)
    {
        mid=(low+high)/2;

        if(a[mid]==key)
        {
            printf("Element Found at position %d",mid+1);
            return 0;
        }

        else if(key<a[mid])
            high=mid-1;

        else
            low=mid+1;
    }

    printf("Element Not Found");

    return 0;
}

Sample Input


Enter number of elements : 7

10 20 30 40 50 60 70

Enter element : 60

Output


Element Found at position 6

Dry Run

Searching 60

Array


10 20 30 40 50 60 70

First Iteration


Low = 0

High = 6

Mid = 3

A[mid] = 40

Since 60 > 40

Search Right Half

Second Iteration


Low = 4

High = 6

Mid = 5

A[mid] = 60

Element Found.

Recursive Binary Search

Binary Search can also be implemented using recursion.

Algorithm


BinarySearch(low, high)

If low > high
    return -1

mid = (low + high) / 2

If key == A[mid]
    return mid

If key < A[mid]
    Search left half

Otherwise
    Search right half

C Program (Recursive Binary Search)


#include <stdio.h>

int binarySearch(int a[], int low, int high, int key)
{
    if(low>high)
        return -1;

    int mid=(low+high)/2;

    if(a[mid]==key)
        return mid;

    if(key<a[mid])
        return binarySearch(a,low,mid-1,key);

    return binarySearch(a,mid+1,high,key);
}

int main()
{
    int a[]={10,20,30,40,50,60,70};

    int n=7;

    int key=30;

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

    if(result==-1)
        printf("Element Not Found");
    else
        printf("Element Found at position %d",result+1);

    return 0;
}

Time Complexity

Case	Complexity
Best Case	O(1)
Average Case	O(log₂ n)
Worst Case	O(log₂ n)

Space Complexity

Iterative


O(1)

Recursive


O(log n)

(due to recursive function calls)

Advantages

✔ Very fast for large datasets.

✔ Reduces search space by half in every iteration.

✔ Efficient algorithm.

✔ Time complexity is O(log n).

</div>

Disadvantages

✘ Works only on sorted arrays.

✘ Sorting may require additional time.

✘ Slightly more difficult than Linear Search.

</div>

Applications

Dictionary word search
Telephone directory
Student record systems
Database indexing
Library management systems
Search engines
Large sorted datasets

Binary Search Visualization

Searching 70


10 20 30 40 50 60 70
          ↑
         40

70 > 40

↓

50 60 70

   ↑
  60

70 > 60

↓

70

Found

📊 Comparison

Feature Linear Search Binary Search
Working Method Sequential Search Divide and Conquer
Array Requirement Sorted or Unsorted Sorted Only
Number of Comparisons More Fewer
Best Case O(1) O(1)
Average Case O(n) O(log n)
Worst Case O(n) O(log n)
Space Complexity (Iterative) O(1) O(1)
Programming Complexity Easy Moderate
Suitable for Large Data No Yes
Suitable for Small Data Yes Yes
Speed Slower Faster

Feature	Linear Search	Binary Search
Working Method	Sequential Search	Divide and Conquer
Array Requirement	Sorted or Unsorted	Sorted Only
Number of Comparisons	More	Fewer
Best Case	O(1)	O(1)
Average Case	O(n)	O(log n)
Worst Case	O(n)	O(log n)
Space Complexity (Iterative)	O(1)	O(1)
Programming Complexity	Easy	Moderate
Suitable for Large Data	No	Yes
Suitable for Small Data	Yes	Yes
Speed	Slower	Faster

Viva Questions

Define Binary Search.
Why must the array be sorted?
Explain the working principle of Binary Search.
Write the Binary Search algorithm.
What is the time complexity of Binary Search?
What is the space complexity of recursive Binary Search?
Differentiate iterative and recursive Binary Search.
Can Binary Search work on an unsorted array? Why?

📘 Types of Sorting

Sorting algorithms can be classified into different types based on where the data is stored, how much memory is used, and whether the relative order of equal elements is preserved.

1. Internal Sorting

Internal Sorting is a sorting technique in which all data to be sorted fits into the computer's main memory (RAM).

</div>

Characteristics

Entire data is available in RAM.
Faster than external sorting.
Suitable for small and medium-sized datasets.

Examples

Selection Sort
Bubble Sort
Insertion Sort
Quick Sort
Heap Sort
Merge Sort (when data fits in memory)

Applications

Student records
Employee databases
Small business applications

2. External Sorting

External Sorting is used when the data is too large to fit into the main memory (RAM). The data is stored on external storage devices such as hard disks or SSDs.

</div>

Characteristics

Data is stored on secondary memory.
Slower because of disk I/O.
Suitable for very large datasets.

Examples

External Merge Sort
Multi-way Merge Sort

Applications

Database systems
Big Data processing
File systems
Search engines

Difference Between Internal and External Sorting

Feature	Internal Sorting	External Sorting
Memory Used	Main Memory (RAM)	Secondary Storage (Disk)
Data Size	Small or Medium	Very Large
Speed	Faster	Slower
Cost	Low	Higher
Examples	Bubble, Selection, Insertion	External Merge Sort

3. In-Place Sorting

An In-Place Sorting algorithm sorts the data without requiring significant extra memory. It uses only a constant amount of additional space.

Space Complexity


O(1)

Characteristics

Uses very little extra memory.
Memory-efficient.
Modifies the original array directly.

Examples

Selection Sort
Bubble Sort
Insertion Sort
Heap Sort
Quick Sort (uses only a small recursion stack)

4. Out-of-Place Sorting

An Out-of-Place Sorting algorithm requires additional memory to sort the elements.

Characteristics

Creates another array or uses extra storage.
Requires more memory.
Often easier to implement.

Examples

Merge Sort
Counting Sort
Radix Sort

Difference Between In-Place and Out-of-Place Sorting

Feature	In-Place	Out-of-Place
Extra Memory	Very Small (O(1))	Additional Memory Required
Original Array	Modified Directly	New Array Used
Memory Efficient	Yes	No
Examples	Bubble, Selection, Insertion	Merge Sort, Counting Sort

5. Stable Sorting

A Stable Sorting algorithm preserves the relative order of equal elements after sorting.

</div>

Example

Before Sorting


Roll   Name    Marks

101    Rahul    80
102    Priya    90
103    Amit     80

After Stable Sorting by Marks


102    Priya    90
101    Rahul    80
103    Amit     80

Notice that Rahul remains before Amit because both have the same marks.

Examples

Bubble Sort
Insertion Sort
Merge Sort
Counting Sort

6. Unstable Sorting

An Unstable Sorting algorithm does not preserve the relative order of equal elements.

</div>

Example

Before Sorting


101 Rahul 80

102 Priya 90

103 Amit 80

Possible Result After Sorting


102 Priya 90

103 Amit 80

101 Rahul 80

The order of Rahul and Amit has changed.

Examples

Selection Sort
Quick Sort
Heap Sort

Classification of Common Sorting Algorithms

Sorting Algorithm	Internal	External	In-Place	Stable
Bubble Sort	✅	❌	✅	✅
Selection Sort	✅	❌	✅	❌
Insertion Sort	✅	❌	✅	✅
Merge Sort	✅*	✅	❌	✅
Quick Sort	✅	❌	✅	❌
Heap Sort	✅	❌	✅	❌
Counting Sort	✅	❌	❌	✅
Radix Sort	✅	❌	❌	✅

Note: Merge Sort can be used as an external sorting algorithm when adapted for data stored on disk.

Memory Diagram


                 Sorting
                     │
     ┌───────────────┴───────────────┐
     │                               │
 Internal Sorting             External Sorting
     │                               │
Data in RAM                 Data on Disk

Another Classification


                    Sorting
                        │
        ┌───────────────┴───────────────┐
        │                               │
     In-Place                     Out-of-Place
        │                               │
 O(1) Extra Space            Extra Memory Needed

Viva Questions

What is Internal Sorting?
What is External Sorting?
Define In-Place Sorting.
Define Out-of-Place Sorting.
What is Stable Sorting?
What is Unstable Sorting?
Which sorting algorithms are stable?
Which sorting algorithms are in-place?
Which sorting algorithm is commonly used for external sorting?
Differentiate Internal and External Sorting.

Quick Revision

Type	Key Point
Internal Sorting	Data fits in RAM
External Sorting	Data stored on disk
In-Place Sorting	Uses O(1) extra memory
Out-of-Place Sorting	Requires extra memory
Stable Sorting	Preserves order of equal elements
Unstable Sorting	May change the order of equal elements

🎓 Exam Tip

Remember these common examples:

Category	Examples
Internal Sorting	Bubble, Selection, Insertion, Quick, Heap
External Sorting	External Merge Sort
In-Place Sorting	Bubble, Selection, Insertion, Heap, Quick
Out-of-Place Sorting	Merge Sort, Counting Sort, Radix Sort
Stable Sorting	Bubble, Insertion, Merge, Counting
Unstable Sorting	Selection, Quick, Heap

📘 Selection Sort

🔷 Definition

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest element from the unsorted portion of the array and places it at the beginning. This process continues until the entire array is sorted.

🔷 Algorithm of Selection Sort


Algorithm: Selection Sort

Step 1: Start

Step 2: Read the array and its size (n).

Step 3: Repeat for i = 0 to n - 2

        a. Assume the first unsorted element is the minimum.
           min = i

        b. Compare a[min] with all remaining elements.

        c. If a smaller element is found,
              min = j

        d. Swap a[i] and a[min].

Step 4: Repeat until the array is sorted.

Step 5: Stop.

🔷 Flow of Selection Sort


Start

↓

Read Array

↓

Find Smallest Element

↓

Swap with First Unsorted Element

↓

Repeat for Remaining Elements

↓

Sorted Array

↓

Stop

🔷 C++ Program for Selection Sort


#include <iostream>
using namespace std;

int main()
{
    int a[100], n, i, j, minIndex, temp;

    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter array elements:\n";

    for(i = 0; i < n; i++)
        cin >> a[i];

    // Selection Sort
    for(i = 0; i < n - 1; i++)
    {
        minIndex = i;

        for(j = i + 1; j < n; j++)
        {
            if(a[j] < a[minIndex])
                minIndex = j;
        }

        // Swap
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }

    cout << "\nSorted Array:\n";

    for(i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

🔷 Sample Input


Enter number of elements: 5

64 25 12 22 11

🔷 Output


Sorted Array:

11 12 22 25 64

🔷 Pass-wise Example

Initial Array


64 25 12 22 11

Pass 1

Smallest element = 11

Swap with first element.


11 25 12 22 64

Pass 2

Unsorted Part


25 12 22 64

Smallest = 12


11 12 25 22 64

Pass 3

Unsorted Part


25 22 64

Smallest = 22


11 12 22 25 64

Pass 4

Unsorted Part


25 64

Already sorted.


11 12 22 25 64

🔷 Total Comparisons

For n elements,

$(n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2}$

For 5 elements:


4 + 3 + 2 + 1 = 10 comparisons

🔷 Time Complexity

Case	Time Complexity
Best Case	O(n²)
Average Case	O(n²)
Worst Case	O(n²)

Explanation

Best Case: Even if the array is already sorted, Selection Sort still scans the remaining elements to find the minimum.
Average Case: Every element is compared with the remaining unsorted elements.
Worst Case: The number of comparisons remains the same as in the best and average cases.

Therefore, the time complexity is O(n²) in all cases.

🔷 Space Complexity

Type	Complexity
Auxiliary Space	O(1)

Explanation

Selection Sort is an in-place sorting algorithm. It uses only a few extra variables (minIndex and temp) regardless of the input size.

Hence, the space complexity is:


O(1)

🔷 Advantages

✔ Easy to understand and implement.
✔ Requires only O(1) extra memory.
✔ Performs fewer swaps than Bubble Sort.
✔ Suitable for small datasets.

🔷 Disadvantages

✘ Inefficient for large datasets.
✘ Time complexity is always O(n²).
✘ Not a stable sorting algorithm.
✘ Does not adapt to already sorted data.

🔷 Applications

Sorting small arrays.
Educational purposes.
Memory-constrained systems.
Situations where minimizing the number of swaps is important.

🔷 Viva Questions

What is Selection Sort?
Why is it called Selection Sort?
How many passes are required for n elements?
What is the best-case time complexity of Selection Sort?
Is Selection Sort a stable sorting algorithm?
What is the space complexity of Selection Sort?
Is Selection Sort an in-place sorting algorithm?

Bubble Sort

📘 Definition

Bubble Sort is a simple comparison-based sorting algorithm in which adjacent elements are repeatedly compared and swapped if they are in the wrong order. After each pass, the largest unsorted element moves (or "bubbles") to its correct position at the end of the array. This process continues until the entire array is sorted.

📝 Algorithm


Algorithm BubbleSort(A, n)

Step 1: Repeat for i = 0 to n − 2
Step 2:     Repeat for j = 0 to n − i − 2
Step 3:         If A[j] > A[j + 1]
Step 4:             Swap A[j] and A[j + 1]
Step 5:         End If
Step 6:     End For
Step 7: End For
Step 8: Stop

💻 C++ Program


#include <iostream>
using namespace std;

int main()
{
    int A[] = {64, 34, 25, 12, 22, 11};
    int n = 6;

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

    cout << "Sorted Array: ";

    for(int i = 0; i < n; i++)
        cout << A[i] << " ";

    return 0;
}

📊 Example

Initial Array


64   34   25   12   22   11

Pass 1


64 34 → Swap
34 64 25 12 22 11

64 25 → Swap
34 25 64 12 22 11

64 12 → Swap
34 25 12 64 22 11

64 22 → Swap
34 25 12 22 64 11

64 11 → Swap
34 25 12 22 11 64

Largest element 64 reaches its correct position.

Pass 2


34 25 → Swap
25 34 12 22 11 64

34 12 → Swap
25 12 34 22 11 64

34 22 → Swap
25 12 22 34 11 64

34 11 → Swap
25 12 22 11 34 64

Pass 3


25 12 → Swap
12 25 22 11 34 64

25 22 → Swap
12 22 25 11 34 64

25 11 → Swap
12 22 11 25 34 64

Pass 4


12 22 → No Swap

22 11 → Swap

12 11 22 25 34 64

Pass 5


12 11 → Swap

11 12 22 25 34 64

✅ Sorted Array


11   12   22   25   34   64

📈 Number of Comparisons (6 Elements)

Pass	Comparisons
Pass 1	5
Pass 2	4
Pass 3	3
Pass 4	2
Pass 5	1
Total	15

Formula

$(n-1)+(n-2)+\cdots+2+1 = \frac{n(n-1)}{2}$

For 6 elements

$\frac{6(6-1)}{2} = 15$

🔄 Number of Swaps (Worst Case)

For a reverse sorted array:


64 34 25 22 12 11

Maximum swaps

$\frac{n(n-1)}{2} = 15$

⏱️ Time Complexity

Case	Complexity
Best Case (Optimized Bubble Sort)	O(n)
Average Case	O(n²)
Worst Case	O(n²)

💾 Space Complexity


O(1)

Only one temporary variable is used for swapping.

⭐ Characteristics of Bubble Sort

Property	Value
Sorting Method	Comparison Based
Stable	✔ Yes
In-place	✔ Yes
Adaptive	✔ Yes (Optimized Version)
Recursive	❌ No
Online	❌ No

Insertion Sort

📘 Definition

Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted array one element at a time. It takes each element from the unsorted portion and inserts it into its correct position in the sorted portion of the array. It is similar to the way people arrange playing cards in their hands.

📝 Algorithm


Algorithm InsertionSort(A, n)

Step 1: Repeat for i = 1 to n − 1
Step 2:     key = A[i]
Step 3:     j = i − 1
Step 4:     While (j ≥ 0) and (A[j] > key)
Step 5:         A[j + 1] = A[j]
Step 6:         j = j − 1
Step 7:     End While
Step 8:     A[j + 1] = key
Step 9: End For
Step 10: Stop

💻 C++ Program


#include <iostream>
using namespace std;

int main()
{
    int A[] = {64, 34, 25, 12, 22, 11};
    int n = 6;

    for(int i = 1; i < n; i++)
    {
        int key = A[i];
        int j = i - 1;

        while(j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            j--;
        }

        A[j + 1] = key;
    }

    cout << "Sorted Array: ";

    for(int i = 0; i < n; i++)
        cout << A[i] << " ";

    return 0;
}

📊 Example

Initial Array


64   34   25   12   22   11

Pass 1 (Key = 34)


64 > 34

Shift 64 to right

34 64 25 12 22 11

Pass 2 (Key = 25)


64 > 25  → Shift

34 > 25  → Shift

25 34 64 12 22 11

Pass 3 (Key = 12)


64 > 12 → Shift

34 > 12 → Shift

25 > 12 → Shift

12 25 34 64 22 11

Pass 4 (Key = 22)


64 > 22 → Shift

34 > 22 → Shift

25 > 22 → Shift

12 < 22 → Stop

12 22 25 34 64 11

Pass 5 (Key = 11)


64 > 11 → Shift

34 > 11 → Shift

25 > 11 → Shift

22 > 11 → Shift

12 > 11 → Shift

11 12 22 25 34 64

✅ Sorted Array


11   12   22   25   34   64

📈 Number of Comparisons (Worst Case – 6 Elements)

Pass	Comparisons
Pass 1	1
Pass 2	2
Pass 3	3
Pass 4	4
Pass 5	5
Total	15

Formula

$1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}$

For 6 elements

$\frac{6(6-1)}{2} = 15$

📦 Number of Shifts (Worst Case)

Worst-case input:


64   34   25   22   12   11

Pass	Shifts
Pass 1	1
Pass 2	2
Pass 3	3
Pass 4	4
Pass 5	5
Total	15

⏱️ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n)
Average Case	O(n²)
Worst Case (Reverse Sorted)	O(n²)

💾 Space Complexity


O(1)

Insertion Sort uses only one extra variable (key), so it requires constant extra memory.

⭐ Characteristics of Insertion Sort

Property	Value
Sorting Method	Comparison Based
Stable	✔ Yes
In-place	✔ Yes
Adaptive	✔ Yes
Recursive	❌ No
Online	✔ Yes

📊 Comparison of Sorting Techniques

The following table compares the three basic sorting algorithms commonly studied in BCA/B.Sc. Computer Science.

Feature	Bubble Sort	Selection Sort	Insertion Sort
Sorting Method	Compares adjacent elements and swaps them	Selects the minimum element and places it in the correct position	Inserts each element into its correct position in the sorted part
Best Case Time Complexity	O(n) (Optimized)	O(n²)	O(n)
Average Case Time Complexity	O(n²)	O(n²)	O(n²)
Worst Case Time Complexity	O(n²)	O(n²)	O(n²)
Space Complexity	O(1)	O(1)	O(1)
Stable	✔ Yes	❌ No	✔ Yes
Adaptive	✔ Yes (Optimized)	❌ No	✔ Yes
In-place	✔ Yes	✔ Yes	✔ Yes
Online Algorithm	❌ No	❌ No	✔ Yes
Maximum Comparisons	n(n−1)/2	n(n−1)/2	n(n−1)/2
Maximum Swaps/Shifts	n(n−1)/2 swaps	n−1 swaps	n(n−1)/2 shifts
Best Suitable For	Small datasets	When minimizing swaps is important	Small or nearly sorted datasets
Efficiency	Low	Better than Bubble (fewer swaps)	Better for nearly sorted data

⭐ Advantages Comparison

Bubble Sort	Selection Sort	Insertion Sort
Easy to understand	Performs minimum swaps	Very efficient for nearly sorted data
Stable sorting	Simple implementation	Stable sorting
Adaptive (optimized version)	Uses constant memory	Adaptive and Online
Good for educational purposes	Good when swap operations are expensive	Excellent for small datasets

❌ Disadvantages Comparison

Bubble Sort	Selection Sort	Insertion Sort
Too many swaps	Not stable	Too many shifts in worst case
Slow for large datasets	Not adaptive	Slow for large datasets
Inefficient for large data	Always performs the same number of comparisons	Performance decreases for reverse-sorted data

Hashing

📘 Definition

Hashing is a technique used to store and retrieve data quickly. It converts a key into a small integer called a hash value (hash code) using a hash function. The hash value determines the location (index) where the data is stored in a hash table.

The main advantage of hashing is that it allows fast searching, insertion, and deletion of data.

📚 Key Terms

1. Key

A key is the value used to identify a record.

Example:


Student Roll Number = 105
Employee ID = 2001

2. Hash Function

A hash function is a mathematical formula that converts a key into an index of the hash table.

One of the most common hash functions is:

\boxed{\text{Hash Index} = \text{Key} \bmod \text{Table Size}}

3. Hash Table

A Hash Table is an array in which records are stored according to their hash values.

Example (Table Size = 10)

Index	Data
0
1	21
2	32
3
4	54
5	15
6
7
8
9	29

🔢 Example of Hashing

Suppose,

Keys


25, 42, 33, 56, 71

Hash Table Size = 10

Hash Function


H(Key) = Key % 10

Step 1

25 % 10 = 5

Store at Index 5

Step 2

42 % 10 = 2

Store at Index 2

Step 3

33 % 10 = 3

Store at Index 3

Step 4

56 % 10 = 6

Store at Index 6

Step 5

71 % 10 = 1

Store at Index 1

Final Hash Table

Index	Data
0
1	71
2	42
3	33
4
5	25
6	56
7
8
9

Different Types of Hash Functions

A hash function is a mathematical function that converts a key into an index (hash value) in a hash table. A good hash function distributes keys uniformly to minimize collisions.

1. Division (Remainder) Method

Definition

The Division Method is the simplest and most commonly used hash function. The hash value is obtained by dividing the key by the table size and taking the remainder.

Formula

H(k) = k \bmod m

Where:

k = Key
m = Size of the hash table

Example 1


Key = 25
Table Size = 10

H(25) = 25 % 10 = 5

Store 25 at Index 5.

Example 2


Key = 42
Table Size = 10

H(42) = 42 % 10 = 2

Store 42 at Index 2.

Example 3


Key = 87
Table Size = 10

H(87) = 87 % 10 = 7

Store 87 at Index 7.

Advantages

Very easy to implement.
Fast computation.
Most widely used in practice.

2. Mid-Square Method

Definition

In the Mid-Square Method, the key is squared, and the middle digit(s) of the square are selected as the hash value.

Steps

Square the key.
Extract the middle digit(s).
Use the extracted digit(s) as the hash value.

Example 1


Key = 25

25² = 625

Middle digit = 2

Hash Value = 2

Example 2


Key = 36

36² = 1296

Middle digits = 29

Hash Value = 29

Example 3


Key = 48

48² = 2304

Middle digits = 30

Hash Value = 30

Advantages

Better distribution of keys than the Division Method.
Reduces clustering.

3. Folding Method

Definition

In the Folding Method, the key is divided into equal-sized parts, and these parts are added together. The final result (or its remainder) becomes the hash value.

Steps

Divide the key into equal parts.
Add the parts.
If necessary, apply the modulo operation.

Example 1


Key = 123456

Divide:

123 + 456 = 579

Hash Value = 579 % 100 = 79

Example 2


Key = 987654

Divide:

987 + 654 = 1641

Hash Value = 1641 % 100 = 41

Example 3


Key = 456789

Divide:

456 + 789 = 1245

Hash Value = 1245 % 100 = 45

Advantages

Suitable for long numeric keys.
Provides better key distribution than simple modulo in many cases.

Collision Resolution

Definition

Collision Resolution is the process of handling collisions so that all keys can be stored and retrieved correctly from the hash table.

There are several collision resolution techniques.

1. Linear Probing (Open Addressing)

Definition

If the calculated index is already occupied, check the next available location until an empty slot is found.

Formula

H_i(k)=(H(k)+i)\bmod m

where:

H(k) = original hash value
i = 0, 1, 2, ...
m = table size

Example

Keys:


25, 35, 45

Hash Function:


H(k)=k%10

Insertion


25 → Index 5

35 → Index 5 occupied → Store at Index 6

45 → Index 5 occupied
      Index 6 occupied
      Store at Index 7

Hash Table

Index	Data
0
1
2
3
4
5	25
6	35
7	45
8
9

Advantages

Easy to implement.
No extra memory required.

Disadvantages

Causes primary clustering.
Search time increases as the table fills.

2. Quadratic Probing

Definition

Instead of checking consecutive locations, the next position is calculated using square numbers.

Formula

H_i(k)=\left(H(k)+i^2\right)\bmod m

Example

Keys:


25, 35, 45

Hash Function:


H(k)=k%10

Insertion:


25 → Index 5

35 → 5 + 1² = 6

45 → 5 + 2² = 9

Hash Table

Index	Data
5	25
6	35
9	45

Advantages

Reduces primary clustering.
Better distribution than linear probing.

Disadvantages

More complex than linear probing.
May not find an empty slot unless the table is designed properly.

3. Double Hashing

Definition

Uses two different hash functions. The second hash function determines the step size for probing.

Formula

H_i(k)=\left(H_1(k)+i\times H_2(k)\right)\bmod m

Example

Let:


H1(k)=k%10

H2(k)=7-(k%7)

For key 35:


H1(35)=5

H2(35)=7-(35%7)=7

Next Index=(5+1×7)%10=2

So, 35 is stored at Index 2.

Advantages

Best distribution among open addressing methods.
Minimizes clustering.

Disadvantages

Requires two hash functions.
More complex to implement.

4. Separate Chaining

Definition

Each index of the hash table stores a linked list (or another dynamic data structure). All keys that hash to the same index are stored in that list.

Example

Keys:


25, 35, 45

All hash to Index 5.

Hash Table


Index 5

25 → 35 → 45 → NULL

Advantages

Simple and effective.
Handles many collisions efficiently.
Table can store more elements than its size.

Disadvantages

Requires extra memory for linked lists.
Slightly slower due to pointer traversal.

Comparison of Collision Resolution Techniques

Technique	Method	Extra Memory	Clustering	Easy to Implement
Linear Probing	Next free slot	❌ No	High	✔ Yes
Quadratic Probing	Square increments	❌ No	Low	Moderate
Double Hashing	Second hash function	❌ No	Very Low	Moderate
Separate Chaining	Linked list at each index	✔ Yes	None	✔ Yes

Time Complexity

Operation	Average Case	Worst Case
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

------------------------------------------

📘 Definition

Double Hashing is a collision resolution technique used in hashing. When a collision occurs, instead of checking the next position sequentially (as in Linear Probing), Double Hashing uses a second hash function to calculate the next index. This reduces clustering and distributes keys more uniformly across the hash table.

Why is it Called "Double Hashing"?

It uses two hash functions:

Primary Hash Function – Finds the initial index.
Secondary Hash Function – Determines the step size for finding the next available position.

Formula

Primary Hash Function:

H_1(k)=k \bmod m

Secondary Hash Function:

H_2(k)=R-(k \bmod R)

where:

k = Key
m = Size of the hash table
R = A prime number smaller than m

Final Probe Formula:

H(k,i)=\left(H_1(k)+i \times H_2(k)\right)\bmod m

where:

i = 0, 1, 2, 3, ...

Example

Given


Hash Table Size (m) = 10

Primary Hash Function:
H1(k) = k % 10

Secondary Hash Function:
H2(k) = 7 - (k % 7)

Keys:
25, 35, 45

Step 1: Insert 25


H1(25) = 25 % 10 = 5

Store 25 at Index 5.

Index	Data
5	25

Step 2: Insert 35

Primary Hash


H1(35) = 35 % 10 = 5

Index 5 is already occupied.

Secondary Hash


H2(35) = 7 - (35 % 7)
       = 7 - 0
       = 7

Now calculate the new index.

For i = 1


New Index

= (5 + 1 × 7) % 10

= 12 % 10

= 2

Store 35 at Index 2.

Index	Data
2	35
5	25

Step 3: Insert 45

Primary Hash


H1(45) = 45 % 10 = 5

Collision occurs again.

Secondary Hash


H2(45)

= 7 - (45 % 7)

= 7 - 3

= 4

For i = 1


New Index

= (5 + 1 × 4) % 10

= 9

Store 45 at Index 9.

Final Hash Table

Index	Data
0
1
2	35
3
4
5	25
6
7
8
9	45

Working Diagram


Keys

25 ─────► Index 5

35 ─► Collision at 5
      │
      ▼
Second Hash Function
      │
      ▼
Index 2

45 ─► Collision at 5
      │
      ▼
Second Hash Function
      │
      ▼
Index 9

Advantages

Reduces primary clustering and secondary clustering.
Provides a more uniform distribution of keys.
Better performance than Linear Probing and Quadratic Probing.
Improves search efficiency.

Disadvantages

Requires two hash functions.
More difficult to implement.
A good secondary hash function is essential.

Time Complexity

Operation	Average Case	Worst Case
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

Comparison with Other Collision Resolution Techniques

Technique	Probe Sequence	Clustering
Linear Probing	+1, +2, +3, ...	High
Quadratic Probing	+1², +2², +3², ...	Moderate
Double Hashing	Uses a second hash function	Very Low

SEM 1	SEM 2	SEM 3
SEM 4	SEM 5	SEM 6

SEM 1	SEM 2	SEM 3
SEM 4	SEM 5	SEM 6

SEM 1	SEM 2	SEM 3
SEM 4	SEM 5	SEM 6

CLASS-4	CLASS-5	CLASS-6
CLASS-7	CLASS-8	CLASS-9
CLASS10	CLASS11 application	CLASS12 application
CLASS11 science	CLASS12 science

C	C++	CORE JAVA	SQL	PYTHON
MS OFFICE	HTML	VISUAL BASIC	advanced java	8085
PROLOG	ASSEMBLY LANGUAGE	JAVA SCRIPT	SHELL PROGRAMMING	R
DIGITAL ELECTRONICS	COMPUTER ARCHITECTURE	DATA STRUCTURE	OPERATING SYSTEM	GRAPH THEORY
DISCRETE MATHEMATICS	NUMERICAL ALGORITHM	AUTOMATA	MICROPROCESSOR	NETWORKING
GRAPHICS	SOFTWARE ENGINEERING	DATABSE	ANALYSIS OF ALGORITHM	IMAGE PROCESSING
ARTIFICIAL INTELLIGENCE	BIG DATA	CLOUD COMPUTING	DATA MINING	INTERNET TECHNOLOGY

Total Pageviews

Thursday, July 2, 2026

WEST BENGAL STATE UNIVERSITY NEP Syllabus for B.Sc. Computer Science Major, Minor and Interdisciplinary SEMESTER 1. CMSACOR01T: Computer Fundamentals and programming with C

WEST BENGAL STATE UNIVERSITY NEP Syllabus for B.Sc. Computer Science Major, Minor and Interdisciplinary SEMESTER 1. CMSACOR01T: Computer Fundamentals and programming with C

Wednesday, July 1, 2026

Recursion

📘 Module 4: Recursion (5 Lectures)

🎓 Module 4: Recursion

Total Lectures: 5

📖 Lecture 1: Introduction to Recursion

🔹 What is Recursion?

🎯 Real-Life Examples

General Syntax

Basic Structure of Recursion

Important Terms

Example 1: Print Numbers from 1 to 5

Output

Example 2: Countdown

📖 Lecture 2: Developing Recursive Definition of Simple Problems

Steps to Develop Recursive Solution

Step 1

Step 2

Step 3

Step 4

Example 1: Factorial

Mathematical Definition

Algorithm

Program

Example 2: Sum of First N Numbers

Example 3: Power

📖 Lecture 3: Advantages and Limitations of Recursion

🌟 Advantages

Applications

⚠ Limitations

Comparison

📖 Lecture 4: Understanding Internal Stack Implementation

Every Recursive Call Creates

Example

Stack Formation

Returning Phase

Visual Diagram

Stack Memory Illustration

📖 Lecture 5: Programs Using Recursion

Program 1: Fibonacci Series

Program 2: Reverse a Number

Program 3: Print Array

Program 4: GCD Using Recursion

Program 5: Decimal to Binary

🎯 Viva Questions

📌 Interview Questions

📘 Tail Recursion

🔹 Definition

🔑 Characteristics of Tail Recursion

📊 General Syntax

Example 1: Print Numbers from 1 to 5

Output

Explanation

Example 2: Countdown

Output

Tail Recursive Factorial

Tail Recursive Version

Output

How It Works

Memory Flow

Tail Recursion vs Non-Tail Recursion

Tail Recursion Example

Non-Tail Recursion Example

Advantages

Limitations

📘 How to Remove Tail Recursion (Convert Tail Recursion to Iteration)

Steps to Remove Tail Recursion

Example 1: Tail Recursive Countdown

Tail Recursive Program

Output

After Removing Tail Recursion (Using while Loop)

Output

Example 2: Print Numbers from 1 to 5

Tail Recursive Version

Iterative Version

Example 3: Tail Recursive Factorial

After Removing Tail Recursion (Using `while` Loop)