GATE Overflow Test Series | Mock GATE | Test 5 | Question: 42

Question

The time complexity of the following C snippet is:

int gate_2020(int n)
{
    for(int i=1; i <= n; i++)
    {
        for(int j=i ; j<=i*i ; j++)
            if(j%i==0)
            {
                for(int k=0; k < j; k++)
                    printf("gate2020");
            }
    }
}

• A. $\Theta(n^3)$
• B. $\Theta (n^2)$
• C. $\Theta(n^4)$
• D. $\Theta(n^5)$

Answer 1

$i=1, 2, 3, 4, \dots n$

$j=i$ to $i^2$

$1 - 1\quad 2 - 4 \quad 3 - 9\quad 4 - 16\quad \dots \quad n-n^2$

$k = 0\;\text{to}\; j$ only if $j\%i=0$

$\implies j$ must be multiple of $i$, that is $ \: 1 \times i, \: \: 2 \times i, \: \: \dots \dots, i \times i$

$1 , 2, 4,  3,6,9 ,4, 8, 12, 16,\ldots, n^2$

$= \displaystyle{} \sum_{i=1}^n \left( i + 2 \times i + 3 \times i + 4 \times i + \dots + i \times i\right)$

$= \displaystyle{} \sum_{i=1}^n i \times \dfrac{i(i+1)}{2}$

$= \displaystyle{} \sum_{i=1}^n\left(\dfrac{i^3}{2} + \dfrac{i^2}{2}\right)$

$=\Theta(n^4)$.

Comments

Sir , in first if conditon only it will give run time error .because of division ny 0 error

---

yes, thats was a typo. Fixed now.

---

yes sir , thank you