Can someone please help me figure out how we reach to (n-1)/4+1 here
1 Answer
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)
5 Comments
Fahdie
okay so assuming the for loop was for( i=0 ; i <=n; i+=4) how would that affect this scenario ?
Alex Lop.
@Fahdie (n-0)/4 + 1 --> n/4 + 1
Fahdie
i am still confused as to how we get to ((n-1)/4 +1) i understand how this works for the above loop but assuming i just had the loop how do i reach to this time complexity function ?
Alex Lop.
@Fahdie OK, lets assume you running index (iterator) is
i and it is running from 0 to N while N=1000. So what is the complexity? In other words how many iterations are there in terms of N. There are 1001 iterations, right? So the complexity is N+1. But now your index i is advanced by 10 instead of 1 (for (int i=0; i <= N; i+=10)). What is the complexity now? how many iterations are there? I would say that there are 1000/10 + 1 iterations ==> 101 which is floor(N/10 + 1).Fahdie
thanks a lot i got it, i was confused as to how each assignment would affect the time complexity