Advance test algorithms

Question

Is there Any short cut to do these questions fast ?

Consider the following code
\[
\begin{array}{l}
\text { sum }=0 ; \\
\text { for }(\mathrm{i}=1 ; \mathrm{i} \leq n ; \mathrm{i}++) \\
\quad \text { for }\left(\mathrm{j}=1 ; \mathrm{j} \leq \mathrm{i}^{*} ; \mathrm{j}+++\right) \\
\quad \text { for }(\mathrm{k}=1 ; \mathrm{k} \leq \mathrm{j} ; \mathrm{k++}) \\
\quad \operatorname{iff}(\mathrm{j} \% \mathrm{i}=0) \text { sum++; }
\end{array}
\]

What is the complexity of the above code?
(a) $\theta\left(\mathrm{n}^{2}\right)$
(b) $\theta\left(\mathrm{n}^{3}\right)$
(c) $\theta\left(\mathrm{n}^{4}\right)$
(d) $\theta\left(\mathrm{n}^{5}\right)$

• A. A
  
• B. B
  
• C. C
  
• D. D
  Answer: D,

Comments

when i=1, j<=1, statement will be executed for 1 time

when i=2, j<=4, the statement will be executed for 4 time

when i=3, j<=9,statement will be executed 9 times

So 1+4+9+16+..... sum of first n squares= n*(n+1)*(2n+1)/6 = O(n^3)

---

@Utkarsh it is O(n^5) (edited) do it again

---

You forgot about 3 for loop

---

 Prince Sindhiya 

Could you please explain how ?

I'm missing somewhere

---

Idk what I forgot but according to me it would be n^3 only

---

j executes for a total of 1+4+9+..+n² times= n(n+1)(2n+1)/6.

now for each value of j, k executes 1+2+3+..+j times. So when j executes n² times, k executes for n²(n²+1)/2 times..

so time complexity is 1+(4*5/2)+(9*10/2)+..+(n²(n²+1)/2) = $\theta$(n⁵)

Is this the right approach to follow?

---

so time complexity is 1+(4*5/2)+(9*10/2)+..+(n²(n²+1)/2) = θ(n⁵)

How was it n^5 ?

---

summation of 1⁴+2⁴+3⁴+...+n⁴ is $\theta$(n⁵)..that is what i know

---

Thank you :)

Got my error.

Answer 1

Answer would be O(n^5)

Comments

I agree! it would be O(n^5) only!

---

which test series is this?