Time complexity of nested 'For loop' with different conditions

Question

Need help understanding how the second loop is executed, I know for the second loop you would multiply by the first loop. First I count the number of instructions and then apply big-oh notation. This is my approach: would j=2*n be executed 2n times, j>=1 n+1, and j-- n times? New to big-oh notation and can't seem to find a list of 'for loops' examples anywhere, would love the feedback and information on where to practice more.

acc=10 \\ 1 

for(i=5;i<=n/2;i++) \\ 1+n/2+n = (1+3n/2)

   for(j=2*n; j>=1; j--) \\ (1+3n/2)(2n+n+1+n)

       acc -= j + acc++; \\ (1+1+1) (2n+n+1+n)

What are those double backslashes? Are they supposed to be comments //? — prapin
– prapin, Commented Feb 6, 2022 at 20:53
j=2*n is executed once; j>=1 is executed 2*n+1 times, j-- is executed 2*n times. But you don't need to be that precise with the counting. k*n is a linear complexity, i.e. O(n). — rturrado
– rturrado, Commented Feb 6, 2022 at 21:12
complexity used to count comparaisons, not operations. If you want to count operations, then you use wrong factor for inner loops, you should multiply by number of loop, not by number of instruction on the line of the loop (so n/2 - 5 instead of 1+3n/2). — Jarod42
– Jarod42, Commented Feb 7, 2022 at 16:39

463035818_is_not_an_ai · Accepted Answer · 2022-02-06 20:58:14Z

2

Constant factors do not matter for asymptotic complexity. The inner loop starts at 2*n and counts down till 1. It has O(n) iterations. The outer loop starts at 5 and counts up till n/2. It has O(n) iterations. In total the nested loop is O(n*n).

answered Feb 6, 2022 at 20:58

463035818_is_not_an_ai

129k11 gold badges116 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

aron_C Over a year ago

Yes, I understand that constant factors do not matter, but I was trying to count the primitive operations executed and then use big-oh notation to remove constants and lower order terms. Sorry I apologize I should have clarified in the very beginning. Which why I wanted to see if I got the count of operations correct on each statement?

463035818_is_not_an_ai Over a year ago

@aron_C sorry, but the only count in your comments I do understand is (1+1+1) for a constant count of operations in the inner loop body, the rest is unclear. I am counting operations to arrive at O(n*n) btw

Collectives™ on Stack Overflow

Time complexity of nested 'For loop' with different conditions

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related