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

56 Consider the following functions:
f(n) = 2n
g(n) = n!
h(n) = n^logn
which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = 2ⁿ g(n) = n! ≅ nⁿ h(n) = n^logn for larger value of n g(n) > f(n) > h(n) so we can conclude that f(n) = O(g(n)) or g(n) = Ω(f(n)) and h(n)= Of(n).

57 The minimum number of comparison required to determine if an integer appears more than n/2 times in a sorted array of n integers is

The minimum number of comparison is logn.

58 Consider the following C functions:

int f l(int n)
{
if(n = = 0 || n = = 1) return n;
else return (2* f1( n –1) + 3 * f1(n – 2));
}
intf2 (int n)
{ int i;
int X[N], Y[N], Z[N];
X[1] = 1; Y[1] = 2;Z[1] = 3;
for( i = 2; i < = n ; i ++ )
{
X[i]=Y[i-l] + Z[i-2];
Y[i]=2*X[i];
Z[i] = 3*X[i];
}
return X[n] ;
}
The running time of f1(n) and f2(n) are

Recurrence relation for f1()is
T (n) = 2T (n–1) + 3 T (n–2)
After solving it would be Θ(1.6)ⁿ) so the largest
value among the options is Θ(2ⁿ).
f2() is simple loop executed n times.
So Θ(n)

59 Consider the following C functions:

int f l(int n)
{
if(n = = 0 || n = = 1) return n;
else return (2* f1( n –1) + 3 * f1(n – 2));
}
intf2 (int n)
{ int i;
int X[N], Y[N], Z[N];
X[1] = 1; Y[1] = 2;Z[1] = 3;
for( i = 2; i < = n ; i ++ )
{
X[i]=Y[i-l] + Z[i-2];
Y[i]=2*X[i];
Z[i] = 3*X[i];
}
return X[n] ;
}
f1(8) and f2(8) return the values

Both function preform same operation so result is same 1640 & 1640

60 What is the number of swaps required to sort n elements using selection sort, in the worst case?

If there are n elements, then in worst case, total swaps will be (n-1) in selection sort. So the number of swaps is Θ(n).
Alternately
The selection sort is similar to bubble sort except it does not swap elements with every move. The sorting algorithm first finds the smallest element in the list and then puts it in to place in single swap. So n swap required for n elements.

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.