Time complexity of common operations, by language

Short answer

Array index and hash lookup are O(1). List search, insertion at the front, and in on a list are O(n). Sorting is O(n log n). Knowing which is which is most of interview optimisation.

#Dynamic array (Python list, JS Array, C# List, Ruby Array, PHP array)

Operation	Complexity
Index access	O(1)
Append to end	O(1) amortised
Insert or delete at front	O(n)
Insert or delete in middle	O(n)
Search by value (`in`)	O(n)
Sort	O(n log n)
Slice of length k	O(k)

#Hash map / dictionary

Operation	Complexity
Get, set, delete	O(1) average
Membership (`in`)	O(1) average
Iterate all	O(n)
Worst case (pathological)	O(n)

#Set

Same as hash map. Union, intersection and difference are O(n + m).

#Sorted structures (tree map, tree set)

Lookup, insert and delete are all O(log n), and iteration comes out in sorted order.

#Heap / priority queue

Operation	Complexity
Push, pop	O(log n)
Peek smallest	O(1)
Build from n items	O(n)

#The two that decide most problems

python

x in some_list      # O(n)  — scans
x in some_set       # O(1)  — hashes

Inside a loop, that is the difference between O(n²) and O(n). It is the most common real fix in these problems.

#String concatenation in a loop

python

s = ""
for part in parts:
    s += part          # O(n²) overall — strings are immutable

Use "".join(parts), StringBuilder in C#, or an array plus join in JavaScript. Interviewers notice this one.

#Sorting to enable something else

Sorting costs O(n log n) but often unlocks an O(n) or O(1)-space follow-up — two pointers, binary search, or grouping adjacent duplicates. If a sort makes the rest linear, it is usually worth it.