Understanding the Time and Space Complexity of a Diamond Pattern in JavaScript

Creating patterns using loops is a common exercise to understand iteration and control flow in programming. In this article, we'll explore a JavaScript program that prints a diamond pattern using stars (*). We'll also provide a Python version of the same pattern, analyze its time and space complexity, and highlight important points to consider.

The Diamond Pattern Code

JavaScript Version

let rows = 5;

// Upper part of the diamond
for (let fh_col = 0; fh_col < rows; fh_col++) {
    let output = "";

    // Add spaces
    for (let ft = fh_col; ft < rows - 1; ft++) {
        output += "  "; // Two spaces for alignment
    }

    // Add left side stars
    for (let mt = 0; mt < fh_col; mt++) {
        output += "* ";
    }

    // Add middle and right side stars
    for (let lt = 0; lt <= fh_col; lt++) {
        output += "* ";
    }

    console.log(output);
}

// Lower part of the diamond
for (let sh_col = 1; sh_col < rows; sh_col++) {
    let output = "";

    // Add spaces
    for (let ft = 0; ft < sh_col; ft++) {
        output += "  ";
    }

    // Add left side stars
    for (let ft = sh_col; ft < rows - 1; ft++) {
        output += "* ";
    }

    // Add middle and right side stars
    for (let ft = sh_col; ft < rows; ft++) {
        output += "* ";
    }

    console.log(output);
}
            

Python Version

rows = 5

# Upper part of the diamond
for fh_col in range(rows):
    output = ""

    # Add spaces
    for ft in range(fh_col, rows - 1):
        output += "  "  # Two spaces for alignment

    # Add left side stars
    for mt in range(fh_col):
        output += "* "

    # Add middle and right side stars
    for lt in range(fh_col + 1):
        output += "* "

    print(output)

# Lower part of the diamond
for sh_col in range(1, rows):
    output = ""

    # Add spaces
    for ft in range(sh_col):
        output += "  "

    # Add left side stars
    for ft in range(sh_col, rows - 1):
        output += "* "

    # Add middle and right side stars
    for ft in range(sh_col, rows):
        output += "* "

    print(output)
            

Time Complexity Analysis

Upper Part of the Diamond

Outer Loop

The outer loop runs rows times to control the number of rows in the upper half of the diamond.

Adding Spaces

The inner loop for adding spaces runs for rows - 1 - fh_col iterations per row, contributing to a time complexity of approximately (rows * (rows - 1)) / 2.

Adding Left Side Stars

This loop runs fh_col times, contributing further to the quadratic complexity.

Adding Middle and Right Side Stars

The loop for adding middle and right side stars runs fh_col + 1 times per row. Over all iterations, this contributes to a time complexity of (rows * (rows + 1)) / 2.

Lower Part of the Diamond

Outer Loop

The outer loop runs rows - 1 times, controlling the number of rows in the lower half of the diamond.

Adding Spaces

The loops for adding spaces are similar to those in the upper part, contributing a quadratic time complexity.

Adding Stars

The loops for adding stars also mirror the upper part, contributing to the same time complexity.

Total Time Complexity

The combined time complexity of the upper and lower parts is O(rows²).

Space Complexity Analysis

The space complexity is determined by the length of the output string, which is proportional to rows for each iteration. Therefore, the space complexity is O(rows).

Important Points

Inevitability of Quadratic Time Complexity: The pattern requires processing a number of characters proportional to rows².

Sequential Inner Loops: The inner loops for spaces and stars are sequential but contribute to overall quadratic growth.

Space Complexity Considerations: Only one row is stored at a time, keeping the space complexity linear.

Optimization Attempts: Methods like .repeat() can simplify code but do not reduce time complexity.

Conclusion

Creating a diamond pattern with stars involves loops with a quadratic time complexity of O(rows²) and a linear space complexity of O(rows). Understanding these performance characteristics is crucial when dealing with larger inputs.