Ruby Built-In Time Complexity: The Interview Cheat Sheet

You open a coding problem, reach for include? on an array to check membership, and the interviewer's face does something subtle. Not a wince. More like a suppressed sigh pulled back behind professionalism. That single method call just told them everything they needed to know.

Ruby is designed to make you feel good. It succeeds at this. The Enumerable module wraps everything in a friendly .each, the syntax reads like English, and suddenly the difference between O(1) and O(n) feels like a style preference. It isn't. One of them gets you the job. The other gets you a polite "we'll be in touch."

Four structures account for nearly all of Ruby's built-in time complexity: Array, Hash, Set, and String. Choosing between them is often the whole interview. Here's where the complexity lives, and the five traps that swallow Ruby candidates alive.

Ruby's Four Structures, Each With One Villain Operation

One quick fact worth burning into memory before we get into the tables: Ruby hashes maintain insertion order, guaranteed since Ruby 1.9. That's occasionally useful for ordered mappings and almost always forgotten right when you need it.

Array: Fast at the Ends, Linear Everywhere Else

Ruby's Array is a dynamic array backed by a contiguous C buffer, with a ring-buffer optimization that makes front operations amortized O(1) rather than O(n). Most devs know push and pop are fast. Fewer know shift and unshift are also fast (thanks to that ring buffer). Almost nobody remembers include? is always, inevitably, mercilessly O(n).

Operation	Complexity	Notes
`push` / `append` / `<<`	O(1) amortized	Buffer doubles on overflow
`pop`	O(1)
`shift`	O(1) amortized	Ring buffer; higher constant than `pop`
`unshift`	O(1) amortized	Ring buffer; higher constant than `push`
`[]` (index access)	O(1)
`first` / `last`	O(1)
`include?` / `member?`	O(n)	Linear scan, always
`index` / `find_index`	O(n)
`each`, `map`, `select`, `reject`, `find`	O(n)
`sort`	O(n log n)	Merge sort internally
`sort_by`	O(n log n)	Keys computed once (Schwartzian transform)
`min` / `max`	O(n)	Single pass
`min_by` / `max_by`	O(n)
`uniq`	O(n)	Hash-backed deduplication
`flatten`	O(total elements)	Recursively flattens nested arrays
`reverse`	O(n)
`bsearch`	O(log n)	Requires sorted array
`insert(i, val)`	O(n)	Shifts elements right
`delete_at(i)`	O(n)	Shifts elements left
`sample`	O(1)

The number to tattoo somewhere: include? is O(n). If you check membership more than once, you want a Set or a Hash, not an array with delusions of grandeur.

bsearch is massively underused in interviews. If your array is sorted and you need a value or a condition boundary, bsearch gives you O(log n) without rolling your own binary search. It exists. Use it.

nums = [1, 3, 5, 7, 9, 11]
nums.bsearch { |x| x >= 7 }  # => 7, O(log n)
nums.include?(7)              # => true, O(n)  # interviewer sighs again

Hash: O(1) Everything (Until Someone Writes `merge` in a Loop)

Ruby's Hash is an open-addressed hash table, and all its core operations are O(1) average case. Rehashing happens automatically when the load factor is exceeded, amortizing the cost over future insertions. This is the fast structure. Use it when you can.

Operation	Complexity	Notes
`h[key]` (read)	O(1) avg	Returns `nil` or default if missing
`h[key] = val`	O(1) amortized	Rehashes on load factor exceeded
`fetch(key)`	O(1) avg	Raises `KeyError` if missing; default block optional
`key?` / `has_key?` / `include?`	O(1) avg	All identical in behavior
`delete(key)`	O(1) avg
`each`, `map`, `select`, `reject`	O(n)
`keys` / `values`	O(n)	Returns new array
`merge(other)`	O(n + m)	Allocates a new hash. Every. Single. Time.
`merge!(other)` / `update`	O(m)	Mutates receiver
`to_a`	O(n)
`min_by`, `max_by`, `sort_by`	O(n log n)	Converts to enumerable first
`any?`, `all?`, `none?`	O(n)	Short-circuits when possible

merge allocates a new hash every time. Every. Time. In a tight loop, that means you're allocating a new hash on every iteration and leaving a trail of garbage for Ruby's GC to cry over. Use merge! or direct assignment instead.

# O(n + m) and creates a new hash (cute outside a loop)
combined = h1.merge(h2)

# O(m) and mutates h1 (what you want inside a loop)
h1.merge!(h2)

# O(1) per key, most explicit
h2.each { |k, v| h1[k] = v }

For a deeper look at why hash table lookups are O(1) and when that breaks down, the hash map time complexity deep dive covers the probability math.

Set: The Structure Most Ruby Candidates Forget Exists

require 'set'  # Always write this. Ruby 3.2+ auto-loads Set, but be explicit.

Set wraps a Hash internally, which is why all its membership operations are O(1) average case rather than the O(n) you'd get from array.include?. The whole point of Set, in one sentence: O(1) include?. If you're checking membership more than once, this is the structure you wanted.

Operation	Complexity	Notes
`add` / `<<`	O(1) avg
`include?` / `member?`	O(1) avg	The entire reason to use Set
`delete`	O(1) avg
`&` (intersection)	O(min(n, m))
`\|` (union)	O(n + m)
`-` (difference)	O(n)
`subset?` / `superset?`	O(n)
`each`	O(n)
`to_a`	O(n)

The trap: converting from Array to Set is O(n). If you do it inside a loop, you've annihilated every advantage you just gained. Convert once before the loop, then query O(1) every time.

words = %w[apple banana cherry]
word_set = words.to_set  # O(n), done once, not n times

# Every lookup is now O(1) (interviewer starts leaning forward)
queries.each { |q| result << q if word_set.include?(q) }

String: The One Character That Changes Everything Is `<`

String#+ allocates a new string on every call; String#<< appends in place at O(1) amortized. These two operations look almost identical. One is fine. The other is an O(n²) time bomb in disguise.

Operation	Complexity	Notes
`length` / `size`	O(1)	Cached by the runtime
`[]` (character access)	O(1)
`+` (concatenation)	O(n)	Allocates a new string every call
`<<` (append)	O(1) amortized	Mutates in place
`include?`	O(n * m)	Naive substring search
`index`	O(n * m)
`split`	O(n)
`chars` / `bytes`	O(n)
`upcase` / `downcase`	O(n)
`reverse`	O(n)
`gsub` / `sub`	O(n)
`strip` / `chomp`	O(n)
`*` (repeat)	O(n * k)

String concatenation in a loop is the most common Ruby performance bug in interview code. It looks completely fine until you think about what + actually does on every iteration.

# O(n²): each iteration copies the whole accumulated string
result = ""
words.each { |w| result = result + w }

# O(n): in-place append, no copy
result = ""
words.each { |w| result << w }

# O(n): cleanest for joining, also fastest
result = words.join

If you write the first version in an interview and the interviewer asks you to optimize it, the answer is two characters: <<.

Five Traps That Cost Ruby Candidates the Offer

Trap 1: `include?` on the Wrong Container

Array's include? and Hash's key? look almost identical but differ by a factor of n. When your membership check lives inside a loop, you've accidentally written O(n²) code that looks completely innocent.

# O(n²): include? does a linear scan on every iteration
seen = []
nums.each { |n| return true if seen.include?(n) }

# O(n): hash lookup is O(1) average. One character change, massive difference.
seen = {}
nums.each { |n| return true if seen.key?(n) }

The fix is changing [] to {}. That's it. The entire interview hangs on that one character sometimes.

Trap 2: Building a String with `+` in a Loop

Each result = result + chunk allocates a new string whose length grows with every iteration. By the end you've built O(n²) work into what looks like a simple loop. You wrote a nested loop with better aesthetics.

Use << or collect into an array and call .join at the end. Both work. Both are O(n). Pick one and move on.

Trap 3: The Shared Default Reference Bug

Hash.new([]) does not give each key its own fresh array. It creates one array and hands the same reference to every missing key. Every key is now pointing at the same object. This is one of those bugs where the code looks completely reasonable until the moment it explodes.

# Bug: all keys share one array, chaos disguised as syntax
h = Hash.new([])
h[:a] << 1
h[:b] << 2
h[:a]  # => [1, 2], not [1]. Welcome to your nightmare.

# Correct: block form creates a new array per key
h = Hash.new { |hash, key| hash[key] = [] }
h[:a] << 1
h[:b] << 2
h[:a]  # => [1]. Much better.

This bites hardest in grouping problems, which show up constantly. Burn this pattern into memory before your interview.

Trap 4: Reaching for `sort` When Top-K Is All You Need

Ruby has no built-in heap, so the natural instinct for top-K problems is array.sort.first(k), which is O(n log n). For small inputs that's fine. For large inputs, a min-heap of size K maintained during the scan gives you O(n log k).

The important part isn't necessarily implementing the heap on the spot. It's knowing to say: "I'm using sort here for simplicity; a min-heap would be O(n log k) if K is much smaller than n." That sentence shows you know the tradeoff. That's what they're scoring.

Trap 5: `sort` vs `sort_by` When the Key Is Expensive

sort_by uses the Schwartzian transform: it computes the key once per element, caches all n keys, then sorts on those cached values. sort { |a, b| expensive(a) <=> expensive(b) } calls expensive O(n log n) times total. These are not the same thing.

# expensive() called O(n log n) times. Oops.
items.sort { |a, b| expensive(a) <=> expensive(b) }

# expensive() called exactly n times, correct
items.sort_by { |x| expensive(x) }

For cheap keys like length or a field lookup, the difference is invisible and nobody will notice. For database reads, regex matches, or file I/O, sort with a block is a trap with a pleasant face.

The Three Gaps Ruby Has No Answer For

Ruby's standard library has no heap, no sorted set (think Java's TreeSet), and no sorted map (think Java's TreeMap). There's no Deque class either, though Array's ring-buffer optimization means you can use it as one with acceptable performance.

For interviews, these are the workarounds worth knowing before you need them:

Top-K elements. Implement a min-heap with an array, or use sort.first(k) and state the complexity caveat explicitly. Don't pretend sorting is free.

Sorted insertion. Maintain a sorted array and use bsearch_index to locate the insertion point, then call insert. The lookup is O(log n); the insertion itself is O(n) due to shifting. If you need O(log n) insertion, say so and describe what a balanced BST would give you.

Ordered iteration by key. hash.sort_by { |k, v| k } gives you a sorted array of pairs in O(n log n). No TreeMap equivalent exists natively.

State these gaps during your interview. Saying "Ruby doesn't have a sorted map here, so I'll sort the pairs once and iterate" shows you understand the tradeoff and are compensating deliberately. Interviewers are not grading whether you remembered every stdlib method. They're grading whether you can reason about performance when the tools you want don't exist.

Practicing this kind of narration out loud is harder than it sounds. SpaceComplexity runs voice-based DSA mock interviews that score your data structure reasoning in real time, so you can train the habit before the actual interview.

Key Takeaways

Array#include? is O(n). Set#include? and Hash#key? are O(1). Use the right one for repeated lookups.
String + allocates a new object every call. << does not. Build strings with << or .join.
Hash.new([]) creates one shared array. Use Hash.new { |h, k| h[k] = [] } for grouping.
sort_by computes keys once. sort with a block recomputes them on every comparison.
Ruby has no heap, sorted set, or sorted map. Know your workarounds and say them out loud.
bsearch gives you O(log n) on sorted arrays without writing binary search from scratch.

Ruby's Four Structures, Each With One Villain Operation

Array: Fast at the Ends, Linear Everywhere Else

Hash: O(1) Everything (Until Someone Writes merge in a Loop)

Set: The Structure Most Ruby Candidates Forget Exists

String: The One Character That Changes Everything Is <

Five Traps That Cost Ruby Candidates the Offer

Trap 1: include? on the Wrong Container

Trap 2: Building a String with + in a Loop