Time Complexity: Prototype chain
O(n)
0
0
Prototype chain in Javascript - Time & Space Complexity
Understanding Time Complexity
When we use the prototype chain in JavaScript, the computer looks up properties step by step along linked objects.
We want to know how the time to find a property changes as the chain gets longer.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
const grandparent = { a: 1 };
const parent = Object.create(grandparent);
parent.b = 2;
const child = Object.create(parent);
child.c = 3;
console.log(child.a); // looks up prototype chain
console.log(child.b);
console.log(child.c);
This code creates a chain of objects and accesses properties that may be on the object or its prototypes.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Searching for a property by checking each object in the prototype chain one by one.
- How many times: At most, the number of objects in the chain until the property is found or the chain ends.
How Execution Grows With Input
As the prototype chain gets longer, the time to find a property grows roughly in a straight line with the chain length.
| Input Size (chain length) | Approx. Operations (property checks) |
|---|---|
| 10 | Up to 10 checks |
| 100 | Up to 100 checks |
| 1000 | Up to 1000 checks |
Pattern observation: The time grows linearly as the chain length increases.
Final Time Complexity
Time Complexity: O(n)
This means the time to find a property grows directly with the number of objects in the prototype chain.
Common Mistake
[X] Wrong: "Looking up a property is always instant, no matter how long the chain is."
[OK] Correct: The computer checks each object one by one until it finds the property, so longer chains take more time.
Interview Connect
Understanding how prototype chains affect lookup time helps you write efficient code and explain how JavaScript works under the hood.
Self-Check
"What if the property is always found on the first object in the chain? How would the time complexity change?"