Hash function concept in Data Structures Theory - Time & Space Complexity

Time Complexity: Hash function concept

O(n)

Understanding Time Complexity

We want to understand how fast a hash function works when it processes data.

The question is: how does the time to compute a hash grow as the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following hash function example.

function simpleHash(input) {
  let hash = 0;
  for (let i = 0; i < input.length; i++) {
    hash += input.charCodeAt(i);
  }
  return hash % 100;
}
    

This code sums the character codes of a string and then reduces the sum to a smaller number.

Identify Repeating Operations

• Primary operation: Looping through each character of the input string.
• How many times: Exactly once for each character, so as many times as the input length.

How Execution Grows With Input

As the input string gets longer, the function does more work, adding each character's code.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The work grows directly with the input size; double the input means double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the hash grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Hash functions always run in constant time no matter the input size."

[OK] Correct: The hash function must look at every part of the input at least once, so time grows with input length.

Interview Connect

Understanding how hash functions scale helps you explain data lookup speeds and why hashing is efficient for many tasks.

Self-Check

"What if the hash function used only the first 5 characters of the input? How would the time complexity change?"