1) A) Write and explain the algorithm of linear search

 Linear search is a searching technique in which each element of a list/array is

checked one by one sequentially until the required key is found or not.
 It does not require a sorted array

Algorithm
1. Start
2. Read n (number of elements)
3. Read array elements
4. Read key (element to search)
5. Set i = 0
6. Repeat while i < n

 If arr[i] == key

• Print "Element found at position i"

• Stop

 Else

• Increment i

7. If loop ends without finding

 Print "Element not found"

8. Stop
Example :
B) What are the advantages of linear search over binary search? Justify your
observation with an example?
Advantages of Linear Search over Binary Search

1. Works on Unsorted Data

 Linear search does not require the array to be sorted.

 Binary search strictly requires sorted data.

2. Works on All Data Structures

 Linear search works on arrays, linked lists, trees, etc.

 Binary search only works efficiently on random-access structures (like arrays).

3. Simpler to Implement

 Linear search is just a single loop.

 Binary search requires mid, low, high pointers

4. No extra space

 Linear search does not require no extra space

 Binary search may require sorting, which takes extra time.

5. Efficient for small datasets

 For small lists, linear search is often faster in practice.

 Binary search has extra overhead.

Example 1 — Unsorted Array (Linear search)

Array: {42, 7, 95, 13, 28, 61, 5} key: 61

Linear Search — Works perfectly:

Step 1: arr[0] = 42 → not found

Step 2: arr[1] = 7 → not found

Step 3: arr[2] = 95 → not found

Step 4: arr[3] = 13 → not found

Step 5: arr[4] = 28 → not found

Step 6: arr[5] = 61 → ✅ Found at index 5

Binary Search — FAILS on unsorted data:

Sorted array needed → {5, 7, 13, 28, 42, 61, 95 }

Key=42

Step 1:

 low = 0, high = 6
 mid = (0 + 6) / 2 = 3
 arr[3] = 28

42 > 28 → Search in right half

Step 2:

 low = 4, high = 6
 mid = (4 + 6) / 2 = 5
 arr[5] = 61

42 < 61 → Search in left half

Step 3:

 low = 4, high = 4
 mid = (4 + 4) / 2 = 4
 arr[4] = 42 ✅ Key Found

Linear search is preferred when:

 Data is unsorted
 Dataset is small

Binary search is better only when data is already sorted and large.
 2) A)Write and Explain the algorithm of Binary Search

Binary Search is a searching algorithm that finds the position of a target element
in a sorted array by repeatedly dividing the search interval into half.

Step 1: Start
Step 2: Input number of elements n
Step 3: Input sorted array arr[n]
Step 4: Input element to search key
Step 5: Initialize low = 0, high = n - 1
Step 6: Repeat while low ≤ high
• Find mid = (low + high) / 2
• If arr[mid] == key
→ Print "Element found at position mid"
→ Stop
• If key < arr[mid]
→ Set high = mid - 1 (search left half)
• Else
→ Set low = mid + 1 (search right half)
Step 7: If low > high
→ Print "Element not found"
Step 8: Stop

Example

Sorted array needed → {5, 7, 13, 28, 42, 61, 95 }

Key=42

Step 1:

 low = 0, high = 6
 mid = (0 + 6) / 2 = 3
 arr[3] = 28
42 > 28 → Search in right half

Step 2:

 low = 4, high = 6
 mid = (4 + 6) / 2 = 5
 arr[5] = 61

42 < 61 → Search in left half

Step 3:

 low = 4, high = 4
 mid = (4 + 4) / 2 = 4
 arr[4] = 42 ✅ Key Found

B) What are the advantages of binary search over linear search? Justify your
observation with an example?

Binary search is generally more efficient than linear search, especially for large datasets. Here
are its key advantages:

1. Faster searching

 Binary search reduces the search space by half each step.

 Linear search checks elements one by one.

Advantage: Much faster for large data.

2. Lower time complexity

 Binary search: O(log n)

 Linear search: O(n)

Advantage: Binary search takes significantly fewer comparisons.

3. Suitable for large datasets

 Works very efficiently when the number of elements is large.

 Linear search becomes slow as size increases.

Advantage: Best for large sorted arrays.

4. Fewer comparisons

 Binary search eliminates half of the elements in each step.

 Linear search may need to check all elements.

Advantage: Reduces number of operations.

Example:

Given Sorted Array: [5, 7, 13, 28, 42, 61, 95]

Key = 42

Using Binary Search:

1. Mid = (low+high)/2=(0+6)/2=3 → go right

2. Mid = 61 → go left
3. Mid = 42 → Found

Total comparisons = 3

Using Linear Search:

 Compare 42 and 5 ->Not found

 Compare 42 and 7 ->Not found
 Compare 42 and 13 ->Not found
 Compare 42 and 28 ->Not found
 Compare 42 and 42 ->key found

Total comparisons = 5

3) A) Find the position of element 92 using binary search method in an array

‘A’ given below: A {11, 5, 21, 3, 92, 17,2,43 }

Binary Search is a searching algorithm that finds the position of a target element in a
sorted array by repeatedly dividing the search interval into half.

Given Array

A = {11, 5, 21, 3, 92, 17, 2, 43}

Binary search requires a sorted array.

First Sort the Array

Sorted A = {2, 3, 5, 11, 17, 21, 43, 92}

(Indexing: 0 to 7)

Search key = 92

Iteration 1:

 low = 0, high = 7
 mid = (0 + 7) / 2 = 3
 arr[3] = 11

92 > 11 → Search right half

Iteration 2:

 low = 4, high = 7
 mid = (4 + 7) / 2 = 5
 arr[5] = 21

92 > 21 → Search right half

Iteration 3:

 low = 6, high = 7
 mid = (6 + 7) / 2 = 6
 arr[6] = 43

92 > 43 → Search right half

Iteration 4:

 low = 7, high = 7
 mid = 7
 arr[7] = 92 - key Found

Key 92 is found at index 7

B) Explain the working of Bubble sort method with an example.

Bubble sort is a simple comparison –based sorting algorithm used in data structure that
repeatedly compares adjacent elements and swaps them if they are in the wrong order and the
largest element bubbles up to its correct position at the end of array.

Algorithm:

1. start
2. read the number of elements n
3. read the array A[ ]
4. for i=0 to n-1
5. for j=0 to n-i-1
6. compare A[j]>A[j+1]
7. if A[j]>A[j+1] swap them
8. repeat until all passes are completed
9. stop

Example

Given Array:
[5, 3, 8, 4, 2]

Pass 1:

 Compare 5 and 3 → swap → [3, 5, 8, 4, 2]

 Compare 5 and 8 → no swap
 Compare 8 and 4 → swap → [3, 5, 4, 8, 2]
 Compare 8 and 2 → swap → [3, 5, 4, 2, 8]

Largest element 8 moves to last

Pass 2:

 Compare 3 and 5 → no swap

 Compare 5 and 4 → swap → [3, 4, 5, 2, 8]
 Compare 5 and 2 → swap → [3, 4, 2, 5, 8]

Next largest 5 moves to correct position

Pass 3:

 Compare 3 and 4 → no swap

 Compare 4 and 2 → swap → [3, 2, 4, 5, 8]

✔ Pass 4:

 Compare 3 and 2 → swap → [2, 3, 4, 5, 8]

Final Sorted Array

[2, 3, 4, 5, 8]

4) A) Explain the basic idea behind insertion sort and how it works. Illustrate

with pseudo code and a suitable example.

Insertion sort is a simple sorting algorithm that builds a final sorted list one element at a time. It
works by repeatedly taking an element from an unsorted portion of list and inserting into its
correct position with in a sorted sub list

Insertion sort works just like arranging playing cards in your hand.

How It Works (Step-by-Step)

1. Assume the first element is already sorted

2. Take the next element
3. Compare it with elements in the sorted part
4. Shift larger elements to the right
5. Insert the element at the correct position
6. Repeat until all elements are sorted

Pseudo Code

InsertionSort(A, n)
{

for i = 1 to n-1
{

key = A[i]
 j= i-1
while (j >= 0 AND A[j] > key)

{
A[j + 1] = A[j]
j=j-1

A[j + 1] = key

Example [5, 3, 8, 1, 4]:

Pass 1 (i=1), key=3: Compare 3 with 5 → shift 5 right → insert 3. Result: [3, 5, 8, 1, 4]

Pass 2 (i=2), key=8: Compare 8 with 5 → 8 > 5, no shift needed. Result: [3, 5, 8, 1, 4]

Pass 3 (i=3), key=1: Compare 1 with 8, 5, and 3 → shift all three → insert 1. Result: [1, 3, 5,
8, 4]

Pass 4 (i=4), key=4: Compare 4 with 8, 5 → shift both → insert 4. Result: [1, 3, 4, 5, 8]

B) Write an algorithm for Selection Sort

Selection sort is a simple comparison –based sorting algorithm that works by repeatedly selecting
minimum element from the unsorted portion of the array and placing it at the beginning

It divides the array into

 A sorted part (left side)

 An Unsorted part (right side)

Algorithm

1. start
2. read the number of elements n
3. read the array A[]
4. for i=0 to n-1
5. set min=1
6. for j=i+1 to n-1
7. if A[j]<A[min] set min=j
8. after the inner loop swap A[i] and A[min]
9. repeat until the array is sorted
10. stop

Example
 5) A) Sort the following numbers in ascending order using Insertion sort. Given

numbers “483, 14, 1416, 153, 254” and write the output after each iteration

 Insertion sort is a simple sorting algorithm that builds a final sorted list one element
at a time.
 It works by repeatedly taking an element from an unsorted portion of list and
inserting into its correct position with in a sorted sub list
 Insertion sort works just like arranging playing cards in your hand.

Given array: 483, 14, 1416, 153, 254

Iteration 1: (i = 1, key = 14)

Compare 14 and 484 ->swap

Array becomes: 14, 483, 1416, 153, 254

Iteration 2 (i = 2, key = 1416)

Compare 1416 and 483 → no swap

Compare 1416 and 14->no swap

Array becomes: 14, 483, 1416, 153, 254

Iteration 3 (i = 3, key = 153)

Compare 153 and 1416 → swap

Compare 153 and 483 → swap

Compare with 14 → no swap

Array becomes: 14, 153, 483, 1416, 254

Iteration 4(i = 4, key = 254)

Compare 254 and 1416 → swap

Compare 254 and 483 → swap
Compare 253 and 153 → no swap

Array becomes: 14, 153, 254, 483, 1416

Final Sorted Array 14, 153, 254, 483, 1416

B) Differentiate between bubble sort and selection sort.

Feature Bubble Sort Selection Sort

Repeatedly swaps adjacent elements Selects the smallest element and
Basic Idea
if they are in wrong order places it in correct position
Method Compares adjacent elements Compares entire unsorted part
Many swaps (after each comparison
Swapping Fewer swaps (only once per pass)
if needed)

Number of Passes n-1 passes n-1 passes

Worst case Time
O(n²) O(n²)
Complexity
Efficiency Less efficient More efficient
Stability Stable Not stable
Space O(1) O(1)

6) A) Sort the following values using Selection (53, 40, 54, 50, 55, 20, 52, 30,

and 15). Illustrate each step of the sorting process

Selection sort is a simple comparison –based sorting algorithm that works by repeatedly selecting
minimum element from the unsorted portion of the array and placing it at the beginning

It divides the array into

 A sorted part (left side)

 An Unsorted part (right side)
Given array: 53, 40, 54, 50, 55, 20, 52, 30, 15

Pass 1 (i = 0)

Smallest element = 15 → swap with 53

Array: sorted :[ 15] unsorted[40, 54, 50, 55, 20, 52, 30, 53]

Pass 2 (i = 1)

Smallest element from unsorted array 20 → swap with 40

sorted array: [15, 20] unsorted array [ 54, 50, 55, 40, 52, 30, 53]

Pass 3 (i = 2)

Smallest element from unsorted array 30 → swap with 54

sorted array [15, 20, 30] unsorted array [50, 55, 40, 52, 54, 53]

Pass 4 (i = 3)

Smallest element from unsorted array is 40 → swap with 50

sorted array[ 15, 20, 30, 40] unsorted array[ 55, 50, 52, 54, 53]

Pass 5 (i = 4)

Smallest element from unsorted array 50 → swap with 55

sorted array [15, 20, 30, 40, 50] unsorted array [55, 52, 54, 53]

Pass 6 (i = 5)

Smallest element from unsorted array 52 → swap with 55

sorted array[ 15, 20, 30, 40, 50, 52] unsorted array[ 55, 54, 53]

Pass 7 (i = 6)

Smallest element from unsorted array 53 → swap with 55

sorted array [ 15, 20, 30, 40, 50, 52, 53] unsorted array[54, 55]

Pass 8 (i = 7)

Smallest element from unsorted array 54 → already in correct position

sorted array: 15, 20, 30, 40, 50, 52, 53, 54, 55

Final Sorted Array: 15, 20, 30, 40, 50, 52, 53, 54, 55
 B) Classify different types of data structures and their applications and
Example?

Primitive Data structures are fundamental data types which are supported by a
programming languages.
Primitive data types are built-in data types that store single values.

Some basic data types are int, float, character, double, Boolean.

Non-primitive data structures are derived data types that can store multiple values or a
collection of data.

Linear Data structure

Linear Data structure arrange data elements sequentially, where each element connects to its
predecessor and successor allowing for single run traversal

Arrays:

An Array is a linear data structure that stores elements of the same data type in
contiguous memory locations.

Declaration: data_type array_name[size];

Ex: int a[10];

Applications of Arrays:

 Storing list of elements

 Used in searching and sorting algorithms

Linked List
A Linked List is a linear data structure in which elements are stored in nodes, and each node
contains:

1. Data
2. Address (link) of the next node

Applications of Linked Lists:

 Dynamic memory allocation

 Used in implementation of stacks, queues

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called
top. It follows LIFO(Last In First Out) manner.
For example: - piles of plates or deck of cards etc.

Stack contains 2 operations

1) Push
2) Pop
Application of stacks: Function calls, Expression Evaluation and UNDO/REDO operations
Queue: Queue is a linear list in which elements can be inserted only at one end called rear and
deleted only at the other end called front.

Applications:

 CPU scheduling
 Printer queue

Non-Linear Data structures

A non-linear data structure is a type of data structure where elements are not arranged
sequentially.
Instead, elements are connected in a hierarchical or network manner.

Trees:

A Tree is a Non-linear data structure which consists of a collection of nodes arranged in

a hierarchical order

Example: Binary Tree

Applications:

 File systems
 Database indexing
 Hierarchical data representation
Graphs:

Example: Social network connections

Applications:

 Routing algorithms (Google Maps)

 Network connections
 Path finding
 7) A) Sort the following numbers in ascending order using Bubble sort. Given
numbers: 483, 14, 1416, 153, 254 and write the output after each iteration.

Bubble sort is a simple comparison –based sorting algorithm used in data structure that
repeatedly compares adjacent elements and swaps them if they are in the wrong order and
the largest element bubbles up to its correct position at the end of array.

Algorithm:

1. start
2. read the number of elements n
3. read the array A[ ]
4. for i=0 to n-1
5. for j=0 to n-i-1
6. compare A[j]>A[j+1]
7. if A[j]>A[j+1] swap them
8. repeat until all passes are completed
9. stop

Given array: 483, 14, 1416, 153, 254

Pass 1

Compare adjacent elements and swap if needed:

 483 > 14 → swap → [14, 483, 1416, 153, 254]

 483 < 1416 → no swap
 1416 > 153 → swap → [14, 483, 153, 1416, 254]
 1416 > 254 → swap → [14, 483, 153, 254, 1416]

Output after Pass 1: 14, 483, 153, 254, 1416

Pass 2

 14 < 483 → no swap

 483 > 153 → swap → [14, 153, 483, 254, 1416]
 483 > 254 → swap → [14, 153, 254, 483, 1416]

Output after Pass 2: 14, 153, 254, 483, 1416

Pass 3

 14 < 153 → no swap

 153 < 254 → no swap

Output after Pass 3: 14, 153, 254, 483, 141

Pass 4

 No swaps → already sorted

Output after Pass 4: 14, 153, 254, 483, 1416

Final Sorted Array: 14, 153, 254, 483, 1416

B) Write an algorithm for Insertion Sort

Insertion sort is a simple sorting algorithm that builds a final sorted list one element at a time. It
works by repeatedly taking an element from an unsorted portion of list and inserting into its correct
position with in a sorted sub list

Insertion sort works just like arranging playing cards in your hand.

Algorithm

Step 1− Assume the first element is already sorted.

Step 2− Pick next element (key)

Step 3− Compare it with elements before it

Step 4 – shift larger elements one position to the right

Step 5 − Insert the key at the correct position

Step 6 − Repeat until list is sorted

Pseudocode

Insertion Sort (A, n)

For i = 1 to n-1 do

key = A[i]

j=i -1

While (j >= 0 AND A[j] > key) do

A[j + 1] = A[j]

j=j -1

End While

A[j + 1] = key

End For

Example
 8) A) What is the worst-case runtime of insertion sort and specify the scenario?

The worst case runtime of insertion sort is O (n²)

Worst-Case Scenario

The worst-case scenario occurs when the input array is sorted in reverse order. For example,

if you are sorting in ascending order, a worst-case input would be [5, 4, 3, 2, 1 ].

In this scenario, every new element being processed must be compared and moved past every single
element already in the sorted portion of the array.

 The first element is considered sorted by default.

 The second element must be compared with and moved past 1 element.

 The third element must be compared with and moved past 2 elements.
 This pattern continues until the nth element, which must be compared with and moved past

n-1 elements

Summing these operations results in approximately n (n-1)/2 comparisons and shifts. In Big O
notation, the highest-order term n² dominates, leading to the O (n²) complexity.

B) Compare best, average and worst case time complexity of insertion, Selection

and Bubble sort?

Sorting Algorithm Best Case Average Case Worst Case

Insertion Sort O(n) O(n²) O(n²)

Selection Sort O(n²) O(n²) O(n²)

Bubble Sort O(n) O(n²) O(n²)

 1. Insertion Sort

 Best Case (O(n))

o When the array is already sorted.
o Only one comparison per element.
 Average Case (O(n²))
o Elements are randomly arranged.
 Worst Case (O(n²))
o When the array is in reverse order.
o Maximum comparisons and shifts.

2. Selection Sort

 Best Case (O(n²))

 Average Case (O(n²))
 Worst Case (O(n²))

Reason:

 Selection sort always scans the entire unsorted part to find the minimum.
 Number of comparisons is always the same regardless of input order.

3. Bubble Sort

 Best Case (O(n))

o When the array is already sorted → no swaps.
 Average Case (O(n²))
o Random order elements.
 Worst Case (O(n²))
o Reverse order → maximum swaps.

9) A) Write about the time complexity with all notation, with its respective graphs?

Time Complexity is the measure of the amount of time an algorithm takes to run as a function of
input size n.

It helps us compare the efficiency of algorithms.

To describe the efficiency and performance of algorithms we used Asymptotic Notations.

1) Big-O Notation
 Represents the worst case running time an algorithm
 It gives upper bound of time complexity.
Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value
on X-Axis and time required is on Y-Axis

In above graph after a particular input value n0 , always C g(n) is greater than f(n) which
indicates the algorithm's upper bound.

The function f(n) =O(g(n)) iff (if and only if) there exit positive constants c and n0 such
that f(n)<=c*g(n) for all n, n>=n0

2) Omega (Ω) Notation

 It gives Lower bound of the time complexity
 Represents the best case running time of an algorithm.

The function f(n) = Ω(g(n)) iff (if and only if) there exit positive constants c and n0 such that
f(n)>=c*g(n) for all n, n>=n0
f(n) = Ω(g(n))
 In above graph after a particular input value n0 , always C x g(n) is less than f(n) which
indicates the algorithm's lower bound.

3) Theta (Θ) Notation

 Represents the avg-case running time of an algorithm

 In this case the execution time serves as a both lower and upper bound on the algorithm
time complexity.
The function f(n) = Θ (g(n)) iff (if and only if) there exist positive constants c1,c2 and n0 such
that c1 *g(n)<= f(n)<=c2 *g(n) for all n, n>=n0
f(n) = Θ(g(n))
 In above graph after a particular input value n0 , always C1 g(n) is less than f(n) and C2
g(n) is greater than f(n) which indicates the algorithm's average bound.

B) Trace the following to search the element 45 is found or not using binary

search technique: 10,20,30,45,50,60,70

Binary Search is a searching algorithm that finds the position of a target element in a
sorted array by repeatedly dividing the search interval into half.

Algorithm:

Step 1: Start
Step 2: Input number of elements n
Step 3: Input sorted array arr[n]
Step 4: Input element to search key
Step 5: Initialize low = 0, high = n – 1
Step 6: Repeat while low ≤ high
• Find mid = (low + high) / 2
• If arr[mid] == key
→ Print "Element found at position mid"
→ Stop
 • If key < arr[mid]
→ Set high = mid - 1 (search left half)
• Else
→ Set low = mid + 1 (search right half)
Step 7: If low > high
→ Print "Element not found"
Step 8: Stop

Given array: 10, 20, 30, 45, 50, 60, 70

Step 1:

 Low = 0, High = n-1=6

 Mid = (0 + 6) / 2 = 3
 Element at index 3 → 45

Step 2:

 Compare: 45 == 45

Element FOUND at position 3

Time Complexity: O (log n)

10) A) Find the time complexity of the following code and explain how it is
Obtained

for (i=0;i<n;i++)
{ for (j=0;j<n;j++)
{ printf (“Value of I =%d”,+i);
}
}

Time Complexity Analysis of the Given Code:

for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
printf("Value of I =%d", i);
}
}
Step-by-Step Analysis:
1. The outer loop runs from i = 0 to i < n, meaning it executes n times.
2. The inner loop runs from j = 0 to j < n, meaning it also executes n times for each iteration of
the outer loop.
3. Inside the inner loop, printf() executes once per iteration.

Total Iterations: For every iteration of outer loop, inner loop runs n times:

The first loop runs in O(n).

The nested loop runs O(n) times inside the first loop.

The total execution count is O(n) × O(n) = O(n²).

The code has a time complexity of O(n²) because of the two nested loops.

Time Complexity = O(n²)

B) Write a code for optimized bubble sort technique.

The optimized bubble sort improves the standard algorithm by introducing a "flag" variable.
This flag detects if any swaps occurred during a pass; if no swaps happen, the array is already
sorted, and the algorithm terminates early

#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
int swapped;
for (i = 0; i < n - 1; i++)
 {
swapped = 0;
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0)
break;
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = {5, 2, 9, 1, 8, 6};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: ");
 printArray(arr, n);
return 0;
}
Output: Original array : 5,2,9,1,8,6
Sorted array : 1,2,5,6,8,9

Time complexity:

Case Complexity
Best Case O(n) (already sorted)
Average Case O(n²)
Worst Case O(n²)

Unit-1 : Short Questions

1) List any four operations on data structure.

Common operations performed on data structures include:

1. Insertion-Adding a new element into the data structure

2. Deletion-Removing an element from the data structure

3. Traversal-Accessing each element one by one

4. Searching-Finding the location of a particular element

2) Write any four applications of data structures

1. Database Management Systems (DBMS)

 Data structures like trees and indexing are used to store and retrieve data efficiently.

2. Operating Systems

 Used in process scheduling, memory management, and file systems.

3. Compiler Design

 Stacks, trees, and symbol tables are used for parsing and expression evaluation.

4. Computer Networks

 Graphs are used to represent networks and find shortest paths (routing).

3) differentiate between Linear and Non-Linear data structure w.r.t. any 2

parameters.

Here is the differentiation between linear and Non-Linear data structures based on 2 parameters:

Parameter Linear Data Structure Non-Linear Data Structure

Elements are arranged sequentially, Elements are arranged hierarchically or in a
Definition
one after another networked fashion
Examples Array, Stack, Queue, Linked List Tree, Graph

4) Define searching and give its types?

Searching is the process of finding the location of a specific element (key) within a data
structure.

Types of Searching:

1. Linear Search (Sequential Search)-Works on both sorted and unsorted data.

2. Binary Search-Works only on sorted data.

5) What are the limitations of linear search?

 Time Consuming for Large Data

 Inefficient Compared to Other Algorithms
 No Use of Data Order
 More Comparisons
 Not Suitable for Repeated Searches
6) What is the fundamental concept of Binary Search?

The fundamental concept of Binary Search is: Divide and Conquer

Binary search repeatedly divides the sorted array into two halves and compares the middle
element with the target (key):

 If middle element = key → Element Found

 If key < middle element → Search in Left Half
 If key > middle element → Search in Right Half

This process repeats until the element is found

7) When linear search is highly inefficient compared to binary search?

 Large Data Sets- Linear search checks each element one by one
 Sorted Data- Linear search does not use sorting advantage
 Repeated Searches- Linear search → repeated full scans
 Worst Case Scenario- When the target element is at the last position or not present, linear
search scans the entire array.
8) Differentiate between binary search and sequential search.

Parameter Binary Search Sequential (Linear) Search

Divides the data into halves (Divide &
Method Checks elements one by one
Conquer)
Data Works on unsorted or sorted
Requires sorted data
Requirement data
Time Complexity O(log n) O(n)
Efficiency Faster for large datasets Slower for large datasets
Comparisons Fewer comparisons More comparisons
9) Define sorting and give its type.

Sorting: Sorting is the process of arranging elements in a specific order, such as ascending or
descending, to improve search and retrieval efficiency.
Types of Sorting:
1. Internal sorting – Sorting performed within the main memory (e.g., Bubble Sort, Quick Sort).
2. External Sorting – Sorting performed using external storage when data is too large for
memory (e.g., Merge Sort, External Merge Sort).
10) List any four sorting techniques

Commonly used sorting techniques are:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort

11) Differentiate between Stable and Un-Stable Sorting

Stable Sorting Unstable Sorting

Maintains the relative order of equal elements Does not maintain order of equal elements

Equal elements remain in the same order as input Equal elements may change positions

Generally uses more memory Generally uses less memory

Bubble Sort, Insertion Sort, Merge Sort Selection Sort, Quick Sort, Heap Sort

12) Explain the term: time complexity

Time Complexity is a measure of the amount of time an algorithm takes to complete as a

function of the input size (n).

Key Points:

 It does not measure actual time in seconds

 It measures the number of operations/steps performed

Types of time complexity:

 best case
 worst case
 average case
13) Explain the term: Space Complexity.

Space Complexity is a measure of the amount of memory space an algorithm requires to

complete as a function of the input size (n).

Key Points:

 It measures the total memory used by an algorithm

 It includes both input data and extra/auxiliary space

14) List the three types of notation for representing complexity.

1. Big-O Notation (O) – Represents the worst-case time complexity.
2. Omega Notation (Ω) – Represents the best-case time complexity.
3. Theta Notation (Θ) – Represents the average-case time complexity.
15) What are Abstract Data Types (ADT)?

Abstract Data Type (ADT) is a logical description of how data is organized and what
operations can be performed on it, without specifying how it is implemented.

Example: Stack ADT

 Operations: push(), pop(), peek()

 Implementation can be:
o Array
o Linked List

16) Define ADT and list the advantages of the same.

Abstract Data Type (ADT) is a logical description of how data is organized and what
operations can be performed on it, without specifying how it is implemented.

Data Abstraction-Hides internal implementation details

Modularity- Programs are divided into independent modules

Reusability-saves time and effort

Reusability- Implementation can be changed without affecting user code