Jagged arrays in C Sharp (C#) - Time & Space Complexity

Time Complexity: Jagged arrays

O(n)

Understanding Time Complexity

When working with jagged arrays, it is important to understand how the time to process them grows as their size changes.

We want to know how the number of steps changes when we access or loop through all elements in a jagged array.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[][] jagged = new int[3][];
jagged[0] = new int[2] {1, 2};
jagged[1] = new int[3] {3, 4, 5};
jagged[2] = new int[1] {6};

for (int i = 0; i < jagged.Length; i++) {
    for (int j = 0; j < jagged[i].Length; j++) {
        Console.WriteLine(jagged[i][j]);
    }
}
    

This code loops through each sub-array inside a jagged array and prints every element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each element inside the nested loops.
• How many times: Once for every element in all sub-arrays combined.

How Execution Grows With Input

As the total number of elements in all sub-arrays grows, the number of operations grows roughly the same way.

Input Size (total elements)	Approx. Operations
10	About 10 prints
100	About 100 prints
1000	About 1000 prints

Pattern observation: The time grows directly with the total number of elements across all sub-arrays.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the loops grows in direct proportion to the total number of elements in the jagged array.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity must be O(n²)."

[OK] Correct: The inner loop runs a different number of times depending on each sub-array's length, so total operations add up to the total elements, not their square.

Interview Connect

Understanding how nested loops over jagged arrays behave helps you explain and analyze real code that handles uneven data structures, a common task in programming.

Self-Check

"What if all sub-arrays had the same length? How would the time complexity change, if at all?"