Column expressions and functions in Apache Spark - Time & Space Complexity

Time Complexity: Column expressions and functions

O(n)

Understanding Time Complexity

When using column expressions and functions in Apache Spark, it's important to know how the time to run grows as data gets bigger.

We want to understand how the number of operations changes when we apply these functions to large datasets.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.sql.functions import col, upper

# Apply upper function to a column
df2 = df.select(col("name"), upper(col("name")).alias("name_upper"))

# Filter rows where name_upper starts with 'A'
df_filtered = df2.filter(col("name_upper").startswith("A"))

# Show results
df_filtered.show()

This code applies a function to transform a column, then filters rows based on the transformed column.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Applying the upper function and filtering on each row's column value.
• How many times: Once for every row in the dataset.

How Execution Grows With Input

Each row is processed individually by the column functions and filter.

Input Size (n)	Approx. Operations
10	About 10 function applications and checks
100	About 100 function applications and checks
1000	About 1000 function applications and checks

Pattern observation: The number of operations grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "Using column functions like upper runs faster than scanning all rows because it's a built-in function."

[OK] Correct: Even built-in functions must process each row, so the time still grows with the number of rows.

Interview Connect

Understanding how column functions scale helps you explain performance when working with big data in Spark.

Self-Check

"What if we added a groupBy aggregation after the column functions? How would the time complexity change?"