While and do-while loops in Kotlin - Time & Space Complexity

Time Complexity: While and do-while loops

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run while and do-while loops changes as the input grows.

Specifically, how many times the loop runs affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var count = 0
while (count < n) {
    println("Count is: $count")
    count++
}

var index = 0
do {
    println("Index is: $index")
    index++
} while (index < n)
    

This code runs two loops: a while loop and a do-while loop, each running until a counter reaches n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The body of each loop runs once per count from 0 up to n - 1.
• How many times: Each loop runs approximately n times.

How Execution Grows With Input

As n grows, the number of times the loops run grows in the same way.

Input Size (n)	Approx. Operations
10	About 10 times each loop runs
100	About 100 times each loop runs
1000	About 1000 times each loop runs

Pattern observation: The work grows directly in proportion to n.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these loops grows linearly as the input size n grows.

Common Mistake

[X] Wrong: "A do-while loop always runs faster than a while loop because it runs at least once."

[OK] Correct: Both loops run about n times here, so their time depends on n, not on the loop type.

Interview Connect

Understanding how loops grow with input size helps you explain your code's efficiency clearly and confidently.

Self-Check

"What if we added a nested loop inside the while loop that also runs n times? How would the time complexity change?"