Calculate the run-time complexity for the worst-case scenario of the following a

Question

Calculate the run-time complexity for the worst-case scenario of the following algorithm:

1. int s = 0;

2. if (N>10){

3. for (int i = 0; i < N; i++){

4. for (int j = i; j < N; j++){

5. s += (i * j) ^ 2;

6. }

7. }

8. }

9. else{

10. for (int i = 0; i < N; i++){

11. for (int j = 0; j < N; j++){

12. s += (i * j) ^ 2;

13. }

14. }

15. }

16. return s

I calculate the following but I'm not sure if I'm doing this correctly.

Line1 = 1 time unit

Line 2 = 1 time unit

Line 16 = 1 time unit

Line 3&4 = N^2

line 5 = 4N

Line 10&11 = N^2

Line 12 = 4N

so T(N) = O(N^2+4N+3) + O(N^2+4N+3)

so T(N) = O(N^2)

This seems really wrong to me, any help correcting where my logic is wrong is appreciated...

Explanation / Answer

Answer:

Runtime analysis:
Line1 = 1 time unit
Line 2 = 1 time unit
Line 16 = 1 time unit
Line 3= N times
Line 4= N(N+1)/2
line 5 =N(N+1)/2
Line 10=N
Line 11=N^2
Line 12 = N^2

Runtime:
so T(N) = O(N(N+1)/2 +3) + O(N^2+3)
so T(N) = O(N^2)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.