Null and duplicate detection in Apache Spark - Time & Space Complexity

Time Complexity: Null and duplicate detection

O(n log n)

Understanding Time Complexity

We want to know how the time needed to find nulls and duplicates changes as the data grows.

How does checking for missing or repeated data scale with bigger datasets?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.sql import SparkSession

spark = SparkSession.builder.getOrCreate()
df = spark.read.csv('data.csv', header=True, inferSchema=True)

# Count nulls in column 'age'
null_count = df.filter(df['age'].isNull()).count()

# Count number of duplicated row groups
duplicate_count = df.groupBy(df.columns).count().filter('count > 1').count()

This code counts how many rows have null values in the 'age' column and how many unique row combinations appear more than once (i.e., number of duplicated groups).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows to check for nulls and grouping all rows to find duplicates.
• How many times: Each row is examined once for null check; grouping requires sorting or hashing all rows once.

How Execution Grows With Input

As the number of rows grows, the time to check nulls grows linearly, and grouping for duplicates grows a bit more due to sorting or hashing.

Input Size (n)	Approx. Operations
10	About 10 checks for nulls, small grouping effort
100	About 100 checks, grouping takes more time but still manageable
1000	About 1000 checks, grouping cost grows but still roughly proportional to n log n

Pattern observation: Null checks grow directly with data size; duplicate detection grows a bit faster due to grouping.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because grouping duplicates involves sorting or hashing all data.

Common Mistake

[X] Wrong: "Checking for duplicates is just as fast as checking for nulls because both scan the data once."

[OK] Correct: Duplicate detection requires grouping or sorting, which adds extra steps beyond a simple scan, making it slower as data grows.

Interview Connect

Understanding how data checks scale helps you explain your approach clearly and shows you know what happens behind the scenes when working with big data.

Self-Check

"What if we used approximate methods like sampling to detect duplicates? How would the time complexity change?"