The real cost of Python and JavaScript built-ins

Why built-ins matter

Interview code is short, so most of the work happens inside built-in operations. If you do not know what they cost, you cannot work out the cost of your own code. Many "time limit exceeded" errors on problem sites come from one innocent-looking line inside a loop.

Python lists, dicts and sets

Dict and set operations are O(1) on average because they use hashing: the key is turned into a number that points almost straight at its slot. In rare bad cases many keys collide and it can be slower, but in practice and in interviews treat them as O(1) average.

Strings are immutable

Immutable means a string cannot be changed after it is made. s += "x" therefore builds a brand-new string and copies the old characters into it. In a loop that adds n pieces, the copying can add up to O(n²) work. CPython sometimes optimises this, but the Python style guide (PEP 8) says not to rely on it. The safe pattern: collect the pieces in a list, then call "".join(pieces) once, which is O(total length).

# Slow pattern: may copy the growing string every time
s = ""
for i in range(5):
    s += str(i) + ","

# Fast pattern: collect parts, join once
parts = []
for i in range(5):
    parts.append(str(i))
print(",".join(parts))   # Output: 0,1,2,3,4

JavaScript arrays, Map and Set

JavaScript arrays behave like Python lists. push and pop work at the end and are O(1) amortised. shift and unshift remove or add at the front and move every other item, so treat them as O(n). includes and indexOf scan the array, O(n). The language standard does not promise exact costs, but these are what engines do in practice.

Map and Set are JavaScript's hash map and hash set, with O(1) average get, set, has and delete. A plain object can also work as a map, but its keys are always turned into strings (so 1 and "1" are the same key), and it inherits keys such as "constructor" and "toString". Use Map when keys come from user data or are not strings; Map also remembers insertion order and has a size property.

const seen = new Set();
for (const x of [3, 1, 4, 1]) {
  if (seen.has(x)) console.log('repeat:', x);
  seen.add(x);
}
console.log([10, 9, 1].sort());                 // [1, 10, 9]  (compared as strings!)
console.log([10, 9, 1].sort((a, b) => a - b));  // [1, 9, 10]

Common mistakes

• x in a_list inside a loop: O(n²) in total. Fix: build a set once, then check x in the_set.
• list.pop(0) or JavaScript shift() in a loop to process a queue. Fix: use collections.deque in Python, or keep a moving "front" index in JavaScript.
• Building strings with += in a long loop. Fix: collect parts in a list and join once.
• Slicing in a loop, such as a[1:] in every step. Fix: use indexes instead of copies.
• Calling sorted() inside a loop. Fix: sort once before the loop, O(n log n) in total.
• Using a JavaScript object as a map for arbitrary keys, or calling sort() on numbers without a compare function. Fix: use Map, and sort numbers with (a, b) => a - b.