CODEWITHSUNDEEP
c++time-complexitybig-ocomplexity-theoryfrequency-analysis
aron_C
aron_C

Reputation: 1

Time complexity of nested 'For loop' with different conditions

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)

Upvotes: 0

Views: 556

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122133

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).

Upvotes: 2

Related Questions