Prototype inheritance in Javascript - Time & Space Complexity

Time Complexity: Prototype inheritance

O(n)

Understanding Time Complexity

When using prototype inheritance in JavaScript, it's important to understand how looking up properties works under the hood.

We want to know how the time to find a property changes as the prototype chain grows longer.

Scenario Under Consideration

Analyze the time complexity of property access using prototype inheritance.

function Person(name) {
  this.name = name;
}

Person.prototype.greet = function() {
  return `Hello, ${this.name}`;
};

const alice = new Person('Alice');
console.log(alice.greet());
    

This code creates an object with a prototype method and accesses that method through the prototype chain.

Identify Repeating Operations

When accessing alice.greet(), JavaScript looks for greet on the object and its prototypes.

• Primary operation: Checking each prototype object for the property.
• How many times: Up to the length of the prototype chain until the property is found.

How Execution Grows With Input

As the prototype chain gets longer, the number of checks to find a property grows.

Prototype Chain Length (n)	Approx. Property Checks
1	1
10	Up to 10
100	Up to 100

Pattern observation: The time to find a property grows linearly with the prototype chain length.

Final Time Complexity

Time Complexity: O(n)

This means the time to access a property depends on how many prototypes JavaScript must check in a row.

Common Mistake

[X] Wrong: "Accessing a property on an object is always instant no matter how long the prototype chain is."

[OK] Correct: JavaScript must check each prototype one by one until it finds the property or reaches the end, so longer chains take more time.

Interview Connect

Understanding prototype inheritance time helps you explain how JavaScript objects work and why deep prototype chains can slow down property access.

Self-Check

"What if we cache the property on the object after the first lookup? How would that affect the time complexity of future accesses?"