Q.1: Explain the concept of time complexity.
Discuss the difference between best-case, worst-case,
and average-case time complexities with examples.
Ans: Time complexity measures how the runtime of an algorithm scales with the size of the
input, n. It's expressed using Big O notation (e.g., O(n), O(log n)) to describe the growth rate
of the operations performed.
Case: definition Example: Linear Search
Linear search Complexity
Best-Case This refers to the minimum possible Element is at the first O(1)
execution time of an algorithm. It position in the array.
represents the most favorable input
configuration, where the algorithm
performs the fewest operations.
Average- This represents the expected runtime Element is somewhere O(n)
case of an algorithm, assuming the input is in the middle on
random average.
Worst- This is the maximum possible runtime Element is not found, or O(n)
Case for an algorithm. It describes the is at the last position.
scenario where the input is in the least
favorable arrangement
Q2: Define topological sorting. Explain how topological sorting is performed using BFS. Provide
an example and show step by step computation.
ans:
Topological Sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG). For every
directed edge from vertex u to vertex v, vertex u must come before vertex v in the ordering. A
topological sort is not possible if the graph has a cycle. It's commonly used in scheduling tasks with
dependencies, like course prerequisites.
Topological Sorting using BFS:
1. Compute in-degrees of all nodes.
2. Enqueue all nodes with in-degree 0.
3. While the queue is not empty:
Dequeue a node u, add it to the result.
For all neighbors v of u, reduce their in-degree by 1.
If in-degree[v] == 0, enqueue v.
Example:
Step 1: Compute In-Degrees
A: 0, B: 1, C: 1 ,D: 2, E: 1, F: 2
Step 2: Initialize Queue
Only vertex A has an in-degree of 0.
Queue
Step 3: Process the Queue:
1. Dequeue A.
Neighbors of A are B and C.
Decrement in-degree of B (1 -> 0). Since it's 0, enqueue B.
Decrement in-degree of C (1 -> 0). Since it's 0, enqueue C.
Queue
2. Dequeue B.
Topological Sort: [A, B]
Neighbor of B is D.
Decrement in-degree of D (2 -> 1).
Queue
A B
3. Dequeue C.
Neighbors of C are D and E.
Decrement in-degree of D (1 -> 0). Since it's 0, enqueue D.
Decrement in-degree of E (1 -> 0). Since it's 0, enqueue E.
Queue
A B C
4. Dequeue D.
Neighbor of D is F.
Decrement in-degree of F (2 -> 1). It's not 0.
Queue
A B C D
5. Dequeue E.
Neighbor of E is F.
Decrement in-degree of F (1 -> 0). Since it's 0, enqueue F.
Queue
A B C D E
6. Dequeue F.
F has no neighbors.
Queue
A B C D E F
Final Topological Sort:
A B C D E F
Topological Sorting using DFS:
Initialization: Create an empty stack to store the result and a visited set to track visited
vertices.
Iterate and Recurse: For each vertex u in the graph, if u has not been visited, perform a
recursive DFS from u.
DFS(u): a. Mark u as visited. b. For each neighbor v of u, if v has not been visited,
recursively call DFS(v). c. After the recursive calls for all neighbors are complete, push u
onto the stack.
Final Result: Once the iteration is complete, the contents of the stack, when popped, will
represent the topological sort.
Example:
Using the same graph, Start a DFS from vertex A (as it's unvisited).
1. DFS(A):
Explore A -> B -> D -> F.
F has no unvisited children. Push F to the stack.
Backtrack to D. D has no other unvisited children. Push D to the stack.
Backtrack to B. B has no other unvisited children. Push B to the stack.
Stack
D
F
Backtrack to A. Now explore A -> C -> E.
E's neighbor F is already visited. Push E to the stack.
Backtrack to C. C's neighbor D is already visited. Push C to the stack.
Backtrack to A. All neighbors are visited. Push A to the stack.
Stack
A
C
E
B
D
F
2. Pop from Stack: Popping all elements from the stack gives the final Topological
Sort.
Stack
A C E B D F
Q.3: Discuss the working principle of Quick Sort. Show the step-by-step sorting process for the array
[8, 3, 1, 6, 2, 7] using Quick Sort.
Ans:
Working Principle of Quick Sort
Quick Sort is a highly efficient, "divide and conquer" sorting algorithm. Its principle is as follows:
1. Pick a Pivot: Choose an element from the array. This element is called the "pivot."
2. Partition: Reorder the array so that all elements with values less than the pivot come before
the pivot, while all elements with values greater than the pivot come after it. After this
partitioning, the pivot is in its final, sorted position.
3. Recurse: Recursively apply the above steps to the sub-array of elements smaller than the
pivot and the sub-array of elements greater than the pivot.
[8 3 1 6 2 7]
Pivot: 7
/ \
[3 1 6 2] [8]
Pivot: 2 Pivot: 8
/ \
[1] [3 6]
Pivot:1 Pivot:6
/ \
[3] [ ]
Pivot:3
Final Sorted Array: [1, 2, 3, 6, 7, 8]
Q4. Compute the time complexity of inserting an element into a sorted
array of size n. Explain how the number of comparisons and shifts affect
the complexity.
Ans:
The time complexity for inserting a new element into a sorted array of size n while
maintaining the sorted order is O(n) in the worst-case scenario.
This complexity arises from two primary operations: locating the insertion point and shifting
existing elements to create space.
Analysis of Operations:
Locating the Insertion Point:
To preserve the sorted property, the correct index for the new element must be
identified. A linear search would compare the new element with existing
elements sequentially. In the worst case (e.g., inserting a value smaller than all
existing elements), this requires n comparisons, contributing O(n) to the
complexity.
Shifting Elements:
Once the insertion point is found, all elements from that point to the end of the
array must be shifted one position to the right to accommodate the new
element.
The worst-case scenario occurs when the new element must be inserted at the
beginning of the array (index 0). This necessitates shifting all n existing
elements. This operation has a complexity of O(n).
Overall Complexity: The total time T(n) is the sum of the costs of each step. T(n) = O(n) +
O(n) + O(1) (using linear search for location).
The overall time complexity is O(n)
Q.5. Analyze the time complexity of finding the maximum element in an
unsorted array of size n. Derive the complexity using step-by-step
reasoning.
Ans: The time complexity of finding the maximum element in an unsorted array of size n is
O(n).
Find-Maximum(Ar, n) Ar[1….N]
Cost times
1. max Ar[1] c1 1
2. for i 2 to n c2 n
3. do if Ar[i]>max c3 n-1
4. then max Ar[i] c4 t
5. return max c5 1
Here, t is the number of times the then block (line 4) is executed, which depends on the input
data.
The worst-case scenario occurs when the array is sorted in ascending order ,In this case, the
max variable must be updated in every single iteration of the [Link] number of times line 4
is executed is t = n-1.
The total running time T(n) is:
T(n) = c₁·1 + c₂·n + c₃·(n-1) + c₄·(n-1) + c₅·1
T(n) = c₁ + c₂n + c₃n - c₃ + c₄n - c₄ + c₅
T(n) = (c₂ + c₃ + c₄)n + (c₁ - c₃ - c₄ + c₅)
The worst-case time complexity is O(n).
Best-Case Analysis
The best-case scenario occurs when the first element of the array is the largest. In this case,
the if condition on line 3 is always false, and the then block on line 4 is never executed. Then
t = 0.
The total running time T(n) is:
T(n) = c₁·1 + c₂·n + c₃·(n-1) + c₄·0 + c₅·1
T(n) = c₁ + c₂n + c₃n - c₃ + c₅
T(n) = (c₂ + c₃)n + (c₁ - c₃ + c₅)
The best-case time complexity is O(n).
Since both the best-case and worst-case running times are O(n), we can conclude that the
overall time complexity of this algorithm is O(n).