CODEWITHSUNDEEP
algorithmtime-complexity
Fahdie
Fahdie

Reputation: 231

For loop Complexity Analysis

Can someone please help me figure out how we reach to (n-1)/4+1 here

enter image description here

Upvotes: 0

Views: 47

Answers (1)

Alex Lop.
Alex Lop.

Reputation: 6875

Let's say you have a loop from 1 to 10. So how many iterations are there?

(10 - 1) + 1 = 10 ==> (n-1) + 1

Actually you always add 1 to such calculations for the first iteration because if you start from 1 to 1 you still do one iteration and it doesn't matter if you increment the iterator by 1, by 2 or by 100.

Now let's assume that our iterator is incremented by 4 each time instead of by 1. So how many iterations are there now? You start from 1, then 5 and then 9... 3 iteration. We have (10-1) as previously but now only each 4th number is counted so it becomes (10-1)/4:

[(10 - 1)/4] + 1 = 3 ==> [(n-1)/4] + 1 (casting to the lower integer)

Upvotes: 1

Related Questions