For loop with step and downTo in Kotlin - Time & Space Complexity

Time Complexity: For loop with step and downTo

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a for loop with a step and downTo changes as the input size grows.

Specifically, how many times does the loop run when counting down with steps?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (i in 100 downTo 1 step 2) {
    println(i)
}
    

This code counts down from 100 to 1, skipping every other number, and prints each value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that runs from 100 down to 1, stepping by 2.
• How many times: It runs about half as many times as the numbers between 100 and 1, because it skips every second number.

How Execution Grows With Input

As the starting number grows, the loop runs fewer times than the total numbers because of the step of 2.

Input Size (n)	Approx. Operations
10	5
100	50
1000	500

Pattern observation: The number of operations grows roughly half as fast as the input size because of the step of 2.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the loop grows in a straight line with the size of the input, even with stepping down.

Common Mistake

[X] Wrong: "Because the loop steps by 2, the time complexity is constant or much smaller than linear."

[OK] Correct: Even though the loop skips numbers, the number of steps still grows proportionally with input size, so it is still linear.

Interview Connect

Understanding how loops with steps and counting down affect time helps you explain how your code scales clearly and confidently.

Self-Check

"What if we changed the step from 2 to 3? How would the time complexity change?"

Practice

1. What does the downTo keyword do in a Kotlin for loop?

easy

A. It makes the loop count forwards from a lower number to a higher number.

B. It makes the loop count backwards from a higher number to a lower number.

C. It skips numbers in the loop by a fixed step.

D. It stops the loop immediately.

Solution

1. Step 1: Understand the purpose of downTo

   The downTo keyword in Kotlin is used to create a range that counts backwards, from a higher number down to a lower number.

2. Step 2: Compare with other options

   It makes the loop count forwards from a lower number to a higher number. describes counting forwards, It skips numbers in the loop by a fixed step. skipping numbers by step, and It stops the loop immediately. stopping the loop immediately, none of which downTo does.

3. Final Answer:

   It makes the loop count backwards from a higher number to a lower number. -> Option B

4. Quick Check:

   downTo = count backwards [OK]

Hint: Remember: downTo means counting downwards [OK]

Common Mistakes:

• Confusing downTo with counting forwards
• Thinking downTo skips numbers
• Assuming downTo stops the loop

2. Which of the following is the correct syntax to loop from 10 down to 1, stepping by 2 in Kotlin?

easy

A. for (i in 10..1 step 2) { println(i) }

B. for (i in 1 downTo 10 step 2) { println(i) }

C. for (i in 10 downTo 1 step 2) { println(i) }

D. for (i in 10 downTo 1 by 2) { println(i) }

Solution

1. Step 1: Identify correct downTo and step syntax

   The correct syntax to count down with steps is for (i in start downTo end step stepValue). for (i in 10 downTo 1 step 2) { println(i) } matches this.

2. Step 2: Check other options for errors

   for (i in 1 downTo 10 step 2) { println(i) } has start < end, resulting in empty range. for (i in 10..1 step 2) { println(i) } uses .. which doesn't support down with step correctly. for (i in 10 downTo 1 by 2) { println(i) } uses by instead of step, which is incorrect.

3. Final Answer:

   for (i in 10 downTo 1 step 2) { println(i) } -> Option C

4. Quick Check:

   Correct syntax = for (i in 10 downTo 1 step 2) { println(i) } [OK]

Hint: Use downTo with step, not by [OK]

Common Mistakes:

• Using by instead of step
• Counting down with .. range
• Reversing start and end values

3. What is the output of the following Kotlin code?

for (i in 8 downTo 2 step 3) {
    print("$i ")
}

medium

A. 8 5 2

B. 8 6 4 2

C. 8 5 3

D. 8 5 2 1

Solution

1. Step 1: Determine the loop values

   The loop starts at 8, counts down to 2, stepping by 3. So values are 8, then 8-3=5, then 5-3=2.

2. Step 2: Confirm the loop stops at 2

   Since 2 is the end value and included, the loop prints 8, 5, and 2.

3. Final Answer:

   8 5 2 -> Option A

4. Quick Check:

   8, 5, 2 with step 3 downTo 2 = 8 5 2 [OK]

Hint: Subtract step each time, stop at end value [OK]

Common Mistakes:

• Including numbers less than end value
• Using wrong step size
• Confusing downTo with ..

4. Identify the error in this Kotlin loop:

for (i in 5 downTo 1 step 0) {
    println(i)
}

medium

A. The downTo keyword is misspelled.

B. There is no error; the code runs fine.

C. The loop should use .. instead of downTo.

D. Step value cannot be zero; it causes a runtime error.

Solution

1. Step 1: Analyze the step value

   The step value is 0, which is invalid and causes a runtime error (IllegalArgumentException).

2. Step 2: Check other options

   downTo is spelled correctly, and using .. would count upwards, not downwards. So options A, C, and D are incorrect.

3. Final Answer:

   Step value cannot be zero; it causes a runtime error. -> Option D

4. Quick Check:

   Step must be positive and non-zero [OK]

Hint: Step cannot be zero; it must be positive [OK]

Common Mistakes:

• Using zero or negative step incorrectly
• Confusing downTo with ..
• Ignoring infinite loop risk

5. You want to print all odd numbers from 15 down to 1 using a Kotlin for loop with downTo and step, without using an if statement. Which code snippet correctly does this?

hard

A. for (i in 15 downTo 1 step 2) { println(i) }

B. for (i in 15 downTo 1 step 1) { if (i % 2 == 1) println(i) }

C. for (i in 15 downTo 1 step 3) { println(i) }

D. for (i in 14 downTo 1 step 2) { println(i) }

Solution

1. Step 1: Understand the goal

   We want to print odd numbers from 15 down to 1. Starting at 15 (which is odd) and stepping by 2 will print all odd numbers downwards.

2. Step 2: Evaluate options

   for (i in 15 downTo 1 step 2) { println(i) } starts at 15 and steps by 2 down to 1, printing 15, 13, 11, ..., 1. for (i in 15 downTo 1 step 1) { if (i % 2 == 1) println(i) } uses step 1 with an if filter (disallowed). for (i in 15 downTo 1 step 3) { println(i) } steps by 3, skipping some odds. for (i in 14 downTo 1 step 2) { println(i) } starts at 14 (even), printing evens.

3. Final Answer:

   for (i in 15 downTo 1 step 2) { println(i) } -> Option A

4. Quick Check:

   Start odd, step 2 downTo 1 = odd numbers [OK]

Hint: Start at odd number, step 2 downTo 1 for odd numbers [OK]

Common Mistakes:

• Starting at even number when printing odds
• Using wrong step size
• Filtering inside loop instead of stepping