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

76 Find a solution to the following recurrence equation
T(n) = T(n/2) + n
T(1) = 1

T (n) = T (n/2) + n
Apply masters method
n^log₂¹ ⇒ n⁰
1 < n
T(n) = O(n)

77 The recurrence relation
T(1) = 2
T(n) = 3T(n/4) + n
Has the solution T(n) equal to

T(n) = 3T (n/4) + n
Apply master’s method
n^log₄³ < n
So O(n)

78 Let T(n) be the function defined by

for n ≥ 2. Which of the following statements is true?

T (n) = T (n/2) + √n
Apply master’s method
n^log₂¹ = n⁰ = 1 < √n
So O(√n)

79 A sorting technique is called stable if

A sorting technique is called stable if it maintains the relative order of occurrence of non distinct elements

80 Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

The worst case time complexity is O (n²)

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.