GATE 2013 CS (CS1) – Question 41

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

What is the asymptotic return value, rather than running time?

int unknown(int n) {
    int i,j,k=0;
    for (i=n/2; i<=n; i++)
        for (j=2; j<=n; j=j*2)
            k=k+n/2;
    return k;
}

$\Theta(n^2)$
$\Theta(n^2\log n)$
$\Theta(n^3)$
$\Theta(n^3\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(n^2\log n)$

Explanation

The outer loop executes Θ(n) times and the inner loop Θ(log n) times. Every iteration adds floor(n/2)=Θ(n) to k. Hence its return value is Θ(n·log n·n)=Θ(n² log n), B, assuming the mathematical asymptotic model without fixed-width overflow.

More Asymptotic Analysis and Time/Space Complexity questions

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…
GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…

All Asymptotic Analysis and Time/Space Complexity questions →