educative.io

Educative

Common Complexity Scenarios_for loop

For-loop with increments of size k:
for (int x = 0; x < n; x+=k) {
//statement(s) that take constant time
}
Running Time for x+=k and x < n is given as floor(n/k)
May i know how this value derived?

Hi @Shameena_Taj,
I am Niaz Ahmad from Educative
let me explain how the number of steps will be equal to the floor of (n/k).

Let’s say n is the condition for our loop.
Let’s take m, which is the number of steps require until n is reached.
And k is the step size.
Then by definition, we say that m*k<n
So the number of steps m will become m<n/k
We take the floor of the number to make it integer because the number of steps has to be an integer, and if we take the ceiling value of float value, it will become greater than n.
Let’s take an example where n=7 and step size k is equal to 2.
According to the above formula m(number of time program will be executed), it will be equal to 7/2, which is 3.5. the number of steps should be an integer, so if we take the floor, then m(number of steps) will become 3.
I hope this answers the question.
Niaz Ahmad | Developer advocate
Educative Inc.