Scribd
Upload
19 views3 pages

University of Chakwal Department of Computer Science and IT

The document discusses various sorting algorithms and their characteristics, including Quick Sort's efficiency and the differences between internal and external sorting. It also compares Kruskal’s and Prim’s algorithms, detailing their preferred use cases based on graph density. Additionally, it analyzes time complexities of different sorting methods and provides a solution using the Master Method.

Uploaded by

ayeshaikram966
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views3 pages

University of Chakwal Department of Computer Science and IT

The document discusses various sorting algorithms and their characteristics, including Quick Sort's efficiency and the differences between internal and external sorting. It also compares Kruskal’s and Prim’s algorithms, detailing their preferred use cases based on graph density. Additionally, it analyzes time complexities of different sorting methods and provides a solution using the Master Method.

Uploaded by

ayeshaikram966
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

University of Chakwal

Department of Computer Science and IT

 Question 1:
1. Why does Quick Sort perform better on average than other simple sorting
algorithms?
Answer:
Quick Sort performs better on average because it uses a divide-and-conquer strategy and works in-place,
reducing memory usage. It also has good cache performance and usually makes fewer comparisons than
bubble or insertion sort.
2. Differentiate b/w Internal Sorting and External Sorting.
Answer:

 Internal Sorting: All data fits into the main memory (RAM). Example: Insertion Sort, Quick Sort.
 External Sorting: Data is too large to fit in RAM; sorting is done using disk storage. Example:
Merge Sort for big files.

3. Differentiate b/w Big-O and Big-Omega Notation.


Answer:

 Big-O (O): Describes the worst-case time complexity.


 Big-Omega (Ω): Describes the best-case time complexity.
Both help analyze algorithm performance under different conditions.

4. Define a recurrence relation. Give one example from a divide-and-conquer


algorithm.
Answer:
A recurrence relation defines a problem in terms of smaller sub-problems.
Example: Merge Sort
T(n) = 2T(n/2) + O(n)
5. In BFS, which data structure is commonly used? What about in DFS?
Answer:

 BFS (Breadth First Search) uses a Queue.


 DFS (Depth First Search) uses a Stack (or recursion, which uses the call stack).

1
University of Chakwal
Department of Computer Science and IT

 Question 2:

a) Difference between Kruskal’s and Prim’s Algorithm. When to prefer one over the
other?
Answer:

Feature Kruskal’s Algorithm Prim’s Algorithm


Type Greedy Greedy
Approach Edge-based Vertex-based
Data Structure Disjoint Set Min-Heap or Priority Queue
Works well on Sparse Graphs Dense Graphs
Cycle Check Needed Not needed

 Kruskal’s is preferred for sparse graphs.


 Prim’s is better for dense graphs.

b) Solve: T(n) = 2T(n/2) + n log n using Master Method


Answer:
Master Theorem form:
T(n) = aT(n/b) + f(n)
Here, a = 2, b = 2, f(n) = n log n

Now, compare f(n) with n^log_b(a):

 log_b(a) = log₂(2) = 1
 f(n) = n log n = n^1 · log n

This fits Case 2 of the Master Theorem:


If f(n) = Θ(n^log_b(a) · log^k n), where k = 1 ⇒
T(n) = Θ(n log² n)

2
University of Chakwal
Department of Computer Science and IT

 Question 3:

Compare Insertion Sort, Heap Sort, and Radix Sort

Criteria Insertion Sort Heap Sort Radix Sort


Works well on small or Any numerical or Non-comparative,
Data Type
mostly sorted data comparable data integers/strings
Time
O(n²), Best: O(n) O(n log n) O(nk) where k = digit length
Complexity
Depends on implementation
Space In-place (O(1)) In-place (O(1))
(O(n + k))
Stability Stable Not stable Stable
Large datasets needing in- Large datasets of integers with
Use Cases Small datasets
place sorting small range

You might also like