educative.io

Common Complexity Scenarios_for loop

Courses
,
#1

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?

#2

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.

#3

Hello!

If n = 7 and k = 2 and when we run the program like following:

    int n = 7;
    int k = 2;

    for (int x = 0; x < n; x += k) {
        System.out.println(x);
    }

The output looks like following
0
2
4
6

Let’s break down the above output a bit:

0
(execute `x < n`) // 0 < 7 so print 0
(execute `x += k`)
2
(execute `x < n`) // 2 < 7 so print 2
(execute `x += k`)
4
(execute `x < n`) // 4 < 7 so print 4
(execute `x += k`)
6
(execute `x < n`) // 6 < 7 so print 6
(execute `x += k`)
8
(execute `x < n`) // 8 > 7 don't print, exit loop.
(execute `x += k`)

We see x += k and x < n run 4 times. Therefore, I think it should ceil(7/2) => ceil(n/k). If x += k and x < n were running 3 times, the loop will end before printing 6. No?

3 Likes
#4

Yes it should be ceil(n/k).

According to my calculations,
Run Time T(n) for x=x+k step, is ceil(n/k). Or we can write it as floor(n/k) + 1

This is because x will be, x=0k, 1k, 2k … mk, (m+1)k. For this, x will increment m+1 times. The last increment from mk to (m+1)k will take place so as to make the exit condition false and break the loop.
Here m=floor(n/k) as seen in the earlier calculations.

Also,
Runtime for x = 0, is 1
Runtime for x<n, is ceil(n/k)+1 or we can write it as floor(n/k) + 2
Runtime for the loop body will be c*ceil(n/k) or we can write it as c*(floor(n/k)+1)

So the total time complexity should be: T(n) = (2+c)*floor(n/k) + 4 + c

This is what my analysis says. Can anyone confirm this value of T(n)? Does it seem right?

1 Like