Avatto > UGC NET COMPUTER SCIENCE > PRACTICE QUESTIONS > Data Structures and Algorithms > Performance Analysis of Algorithms and Recurrences

Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

91 Suppose P, Q, R, S, T are sorted sequences having lengths 20,24,30,35,50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is __________.

20, 24, 30, 35, 50
Step 1 : We take

Comparisons = (20 + 24 – 1) Max = 43
Step 2 :

Total comparison = 43 + (65 – 44) = 64
Step 3 :

Total comparison = 64 + 19 = 83
Step 4 :

Total comparison = 93 + 65 = 158
= 158 + 93 + 64 + 43 = 358

92 Give the correct matching for the following pairs:

List-I		List-II
A.	O(logn)	P.	Selection
B.	O(n)	Q.	Insertion sort
C.	O(n log n)	R.	Binary search
D.	O(n²)	S.	Merge sort

Codes:
(a) A – R B – P C – Q D – S
(b) A – R B – P C – S D – Q
(c) A – P B – R C – S D – Q
(d) A – P B – S C – R D – Q

Selection sort = O (n²)
Insertion sort = O (n²) or (O(n) in best case)
Binary Search = O (logn)
Merge Sort = O (n logn)
None of the options is true

93 Suppose we want to arrange the n numbers stored in an array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

When we have ‘n’ numbers stored in an array, we have to swap all positive number with negative number so in worst case positive numbers will be n/2,

94 If T1 = O(1), give the correct matching for the following pairs:

T(n) = T_(n–1)+n ⇒ O(n²)
T(n) = T_(n/2) + n ⇒ O(n)
T(n) = T_(n/2) + n logn ⇒ O(n logn)
T(n) = T_(n–1) + logn ⇒ O(log²n)

95 If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1...n?

There are n(n-1)/2 pairs. So average inversions are

Your Progress

0%

Start Practising!

You've answered 0 of 127 questions in this topic.

Practice Spotlight

Build momentum in Performance Analysis of Algorithms and Recurrences

Start with a short question set, review every explanation, and revisit difficult questions before moving ahead.

Day 4 / 10

Global Spotlight

Build Your First Streak

Complete one short Performance Analysis of Algorithms and Recurrences session today, then return tomorrow. Consistency matters more than a long first session.

Day 7 / 10

Question Spotlight

Question:

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

A. O(n)
B. O(nlogn)
C. O(n^3/2)
D. O(n³)

Correct answer: D

Explanation:

The time complexity of computing the transitive closure of binary relation on a set of n elements is O (n3).

Click to view the complete question details

Day 4 / 10 Open this question

Community Insight

Based on 44 saved attempts

Most Attempted TopicTrees
Most Challenging TopicAdvanced Algorithm
Average Accuracy84%

Featured Question

(Based on recent community answers)

Q. #26901New

The time complexity of computing the transitive closure of a binary relation on a set…

Try This Question →

This Week's Challenge

Complete 20 questions and set the community benchmark!

0 / 20 Start Challenge →

Why Practice with Avatto?

High Quality MCQsExam-focused questions with accurate answers

Detailed ExplanationsStep-by-step explanations to enhance learning

Latest Exam PatternBased on updated syllabus and pattern

Performance AnalyticsTrack performance and improve weak areas

100% Free PracticePractice unlimited questions for free

Forgot your password?

I agree with the Terms.