Algorithms Complexity

Question

Comments

Is it thetha(n³⁾?

---

The answer is O(n^5)

---

@phaneendrababu explain!

---

@phaneendrababu

Even if we remove the if(j%i) statement we obtain thetha(n⁴)

---

For a value i=m such that  0<=m<=n

j ranges from 0 to m²;

The third loop is run when j=m,2m,3m,....m² so total m times, and for remain m²-m iterations of j, third loop is not executed hence constant time for them.

Hence the first time the loop run for m iterations, then 2m, 3m,.....m²

Total: 1m+2m+3m+...+m²  + the remaining m²-m iterations of j which run for $\Theta$(1) = m[1+2+...+m]+m²=$\Theta$(m³)

When the algorithm is run for all values of i

We get  0³+1³+2³+3³+...n³

=$\Theta$(n⁴)

---

The first outer loop runs 'O(n)' times.The first inner loop runs 'O(n^2-n)' times for each iteration.The second inner loop depends on j value.So,it runs 'O(n^2-n)' times .

Total time complexity::O(n)*O(n^2-n)*O(n^2-n)=O(n^5).

---

@phaneendrababu

But the second loop doesnt always run for n^2 iterations.

---

but at least it runs half of the times of the second loop,by doing amortized analysis also we are not getting O(n) for that.

---

@sakharam

your explanation was correct, it is θ( n⁴ ) only

@phaneendrababu

θ( n⁴ )  = O(n⁵) ----- it is also correct, but we choose lower bound always ===> it is θ( n⁴ )

---

The outer loop has 'n' iterations.For each outer loop the first inner loop has 'n^2' iterations,For some iterations of the first inner loop the second inner loop has 'n(n+1)/2' iterations. So,the time complexity is O(n)*O(n^2)*O(n^2)==>O(n^5).

---

Look at this once , this is from Narasimha Karumanchi ,IIT Bombay 

Answer 1

Answer is  O(n⁴)