GATE 2017 CS (CS2) – Question 48

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

Find the time complexity.

int fun(int n) {
    int i,j;
    for (i=1; i<=n; i++) {
        for (j=1; j<n; j+=i) {
            printf(" %d %d",i,j);
        }
    }
}

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n\log n)$

Explanation

For each i, the inner loop takes Θ(n/i) iterations, up to constant endpoint effects. Summing over i gives $\Theta(n\sum_{i=1}^n1/i)=\Theta(nH_n)=\Theta(n\log n)$. Thus C; the increasing step size prevents quadratic work.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2012 CS (CS1) Q15 – Find the worst-case search time in a balanced BST with n2n elements.
GATE 2012 CS (CS1) Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always…
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…

All Asymptotic Analysis and Time/Space Complexity questions →