CODEWITHSUNDEEP
algorithmfor-looptime-complexity
penultimatehello
penultimatehello

Reputation: 31

Time complexity of for loop where i starts with a variable (not 1 or 0)

I want to know the time complexity of a for loop for(i=m;i<=n;i++) where m and n are both variables. I am thinking it will be O(n-m) as the loop is dependent on both values of m and n. Please guide me !

Upvotes: 3

Views: 336

Answers (2)

Zabuzard
Zabuzard

Reputation: 25903

Explanation

Assuming your loop only executes statements that run in constant time, i.e. O(1), you simply have to count the amount of loop iterations.

Your loop head

 for (i = m; i <= n; i++)

will generate iterations with i being m, m + 1, m + 2, m + 3, ... , n - 2, n - 1, n. So from m to n, both ends inclusive.

So exactly n - m + 1 iterations (simple example 2, 3, 4, 5 with 5 - 2 + 1 = 4).

Thus, the asymptotic time complexity is

O(n - m + 1) = O(n - m)

Like you said.

Upvotes: 2

Majed Badawi
Majed Badawi

Reputation: 28414

Yes indeed, it is O(n-m+1) since it will start at m and reaches n in the worst-case scenario.

Upvotes: 1

Related Questions