GATE 2012 CS (CS1) – Question 28

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

W(n) and A(n) are worst-case and average running times on inputs of size n. Which always holds?

$A(n)=\Omega(W(n))$
$A(n)=\Theta(W(n))$
$A(n)=O(W(n))$
$A(n)=o(W(n))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $A(n)=O(W(n))$

Explanation

An average over inputs cannot exceed the maximum running time on those inputs, so A(n)≤W(n) and A(n)=O(W(n)), C. Equality in Θ need not hold, while little-o fails when average and worst case have the same order.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2013 CS (CS1) Q40 – How many elements can heap sort sort in ( n) time?
GATE 2013 CS (CS1) Q41 – What is the asymptotic return value, rather than running time?
GATE 2011 CS (CS1) Q47 – Find increasing asymptotic growth order for f 1(n)=2n, f 2(n)=n3/2, f 3(n)=n 2n, f 4(n)=n…
GATE 2010 CS (CS1) Q22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find…
GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find…
GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial…

All Asymptotic Analysis and Time/Space Complexity questions →