Nested functions in Swift - Time & Space Complexity

Time Complexity: Nested functions

O(n²)

Understanding Time Complexity

When we use nested functions, we want to know how the time it takes to run grows as the input gets bigger.

We ask: How does calling a function inside another affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func outerFunction(_ n: Int) {
    func innerFunction(_ m: Int) {
        for i in 0..

This code defines a function inside another. The outer function calls the inner one multiple times, each time with a different number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop inside innerFunction that runs from 0 to m.
• How many times: The outer loop calls innerFunction n times, with m changing from 0 up to n-1.

How Execution Grows With Input

Each time the outer loop runs, the inner loop runs more times than before.

Input Size (n)	Approx. Operations
10	About 45 prints (0+1+2+...+9)
100	About 4,950 prints
1000	About 499,500 prints

Pattern observation: The total work grows roughly like the sum of numbers from 0 to n-1, which grows much faster than just n.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the input size, the work roughly quadruples because of the nested calls.

Common Mistake

[X] Wrong: "Since the inner function runs inside the outer loop, the time is just O(n) because it looks like one loop inside another."

[OK] Correct: The inner loop runs a different number of times each call, adding up to much more than just n times. It's the total sum of all inner loops that matters.

Interview Connect

Understanding how nested functions affect time helps you explain your code clearly and shows you can think about efficiency in real problems.

Self-Check

"What if the inner function always ran a fixed number of times, say 10, no matter the input? How would the time complexity change?"