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

1 A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the m^th record is the first record to result in collision is

A
B
C
D

Probability for the first record not colliding is x/x.
Probability for the second record not colliding is x-1/x.
(This is because one place is already occupied, So, favorable number of cases is x-1).
Probability for the third record not colliding is x-2/x.
Probability for the (m-1)th record not colliding is

.
Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So,

2 Which decision procedure has at least doubly exponential time complexity?

3 The running time T(n), where 'n' is the input size of a recursive algorithm is given
T(n) = c + T(n-1), if n > 1
= d, if n ≤ 1
The order of the algorithm is

Recursively applying the relation, we finally get
T(n + 1) = c(n - 1) + T(1)
= c(n - 1) + d
hence order is n.

4 Which of the following shows the correct relationship among some of the more common computing times for algorithms?

5 F(x) = (7x⁶ + 3x⁴ + 17x + 9)/(0.01x³ * x^-1) is Big - O of WHAT?

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.