Scribd
Upload
2 views5 pages

Question

The time complexity of the given nested loop is O(n^2). The document also outlines the step-by-step process of using merge sort to sort the array [10,3,7,15,2,8,5,1], detailing the divide, merge single elements, merge sorted pairs, and final merge stages. The final sorted result of the array is [1,2,3,5,7,8,10,15].

Uploaded by

metwalym220
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
2 views5 pages

Question

The time complexity of the given nested loop is O(n^2). The document also outlines the step-by-step process of using merge sort to sort the array [10,3,7,15,2,8,5,1], detailing the divide, merge single elements, merge sorted pairs, and final merge stages. The final sorted result of the array is [1,2,3,5,7,8,10,15].

Uploaded by

metwalym220
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

What is the time complexity of the following loop?

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

for (j = 0; j < n; j++) {

print (i, j);

Answer: O(n2)
Show the step-by-step how merge sort is used to sort the following array: [10,3,7,15,2,8,5,1]

1 – Divide

• [10,3,7,15] and [2,8,5,1]


• [10,3] [7,15] and [2,8] [5,1]
• Finally: [10] [3] [7] [15] [2] [8] [5] [1]

2 – Merge single elements

• [10] + [3] → [3,10]


• [7] + [15] → [7,15]
• [2] + [8] → [2,8]
• [5] + [1] → [1,5]
• Finally: [10,3] [7,15] [2,8] [5,1]

3 – Merge sorted pairs

• [3,10] + [7,15] → [3,7,10,15]


• [2,8] + [1,5] → [1,2,5,8]
• Finally: [3,7,10,15] & [1,2,5,8]

4 – Final Merge

• Merge [3,7,10,15] with [1,2,5,8]

Compare 3 vs 1 → take 1

Compare 3 vs 2 → take 2

Compare 3 vs 5 → take 3

Compare 7 vs 5 → take 5

Compare 7 vs 8 → take 7

Compare 10 vs 8 → take 8

Remaining → 10, 15
Final Result: [1,2,3,5,7,8,10,15]

You might also like