Hash tables (dictionaries) in PowerShell - Time & Space Complexity

Time Complexity: Hash tables (dictionaries)

O(n)

Understanding Time Complexity

When using hash tables (called dictionaries in PowerShell), it's important to know how fast operations like adding or finding items are. We want to understand how the time it takes changes as the number of items grows.

How does the speed of looking up or adding a value change when the dictionary gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$dict = @{}
for ($i = 0; $i -lt $n; $i++) {
    $dict["key$i"] = $i
}
$value = $dict["key500"]
    

This code creates a dictionary, adds n key-value pairs, then looks up one value by its key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop adding n items to the dictionary.
• How many times: Exactly n times for insertion; one time for lookup.

How Execution Grows With Input

As the number of items n grows, adding each item takes about the same time, so total time grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 insertions + 1 lookup
100	About 100 insertions + 1 lookup
1000	About 1000 insertions + 1 lookup

Pattern observation: The total time grows linearly with n because each insertion is quick and independent.

Final Time Complexity

Time Complexity: O(n)

This means adding n items takes time proportional to n, and looking up a single item is very fast, almost constant time.

Common Mistake

[X] Wrong: "Looking up a key in a dictionary takes time proportional to the number of items."

[OK] Correct: Actually, hash tables let us find items very quickly, no matter how many items there are, so lookup time stays almost the same even if the dictionary grows.

Interview Connect

Understanding how hash tables work and their time behavior is a key skill. It helps you write fast scripts and shows you know how to handle data efficiently in real tasks.

Self-Check

"What if we changed the dictionary to a list and searched for a key by checking each item? How would the time complexity change?"