Time Complexity Basics
Fast recall
Quick revision
Core answer
3n + 20 is O(n), but it does not mean constants and built-in work are irrelevant in real code. In Ruby, count the cost of methods inside loops: an Array membership scan is O(n), while ordinary Hash or Set membership is expected O(1), so replacing repeated array search can change O(n²) work into expected O(n) with O(n) extra space.Whether you can name O(1)/O(log n)/O(n)/O(n log n)/O(n^2), count loops in Ruby, and pick the lower-complexity structure (hash for O(1)).
Counting only outer loops (miss nested each as O(n^2)), or calling sort O(n) (it's O(n log n)).
Time complexity = how runtime grows with n: O(1) hash lookup, O(log n) binary search, O(n) each, O(n log n) sort, O(n^2) nested each. Pick the lower-complexity structure.
Interview-ready guide
Interview answer
Time complexity is a growth model: it asks how work changes when input size n grows. Space complexity asks how much additional memory the algorithm needs beyond its input and required output. Big O provides an upper growth class, so a fixed number of full passes is still O(n), while testing every pair is O(n²).
I first define n and the dominant operation. Two loops are not automatically quadratic: consecutive loops add to O(n + n), and two pointers that only move forward can share O(n) total work. Nested loops multiply only when the inner range is repeated independently for each outer iteration.
Ruby's expressive methods still perform work. For example, seen_array.include?(item) scans up to n elements. Calling it for every input can be O(n²). Using a Hash or Set for membership gives expected constant-time lookup in ordinary conditions, making the complete scan expected O(n) while storing up to n keys.
Other hidden costs include sorting at roughly O(n log n) for interview reasoning, allocating arrays with map or select, copying substrings, and building intermediate chains. A short Ruby expression can therefore use more time or memory than a longer single-pass loop.
Complexity does not replace measurement or correctness. Small inputs may favour simpler code, hash operations have memory and key-cost overhead, and implementation details can vary. I state worst or expected case explicitly, include auxiliary space, and then test performance with realistic data if the choice matters in production.
Time Complexity Basics
Direct Answer
Time complexity describes how the number of operations grows as input size grows; space complexity describes additional memory growth. Big O keeps the dominant growth term, so 3n + 20 is O(n), but it does not mean constants and built-in work are irrelevant in real code. In Ruby, count the cost of methods inside loops: an Array membership scan is O(n), while ordinary Hash or Set membership is expected O(1), so replacing repeated array search can change O(n²) work into expected O(n) with O(n) extra space.
Deep Dive & Architecture
Choose a size variable that represents the growing input: number of array elements, vertices and edges, rows and columns, or characters and bytes. Multiple dimensions should remain separate when they can grow independently; scanning every item from two arrays is O(n + m), not automatically O(n).
Amortised analysis handles occasional expensive operations. Appending to a dynamic array may sometimes grow its storage and copy elements, but a sequence of appends can still have constant amortised cost per append. Expected analysis describes hash behaviour under ordinary distribution; it should be labelled rather than presented as an unconditional worst-case guarantee.
Space needs the same care. A result array required by the question is output space, while a frequency hash is auxiliary space. Recursive call stacks, copied slices, decorated sort keys, and enumerator pipelines can all contribute even when no variable is named buffer.
A useful optimisation removes the repeated dimension. The brute-force duplicate check compares each item with later items. A hash summary carries previous membership forward, so the algorithm pays once per element instead of restarting a search. The gain follows from preserved state, not from Ruby syntax alone.
Code Example
def first_duplicate(values)
seen = {}
values.each do |value|
return value if seen.key?(value)
seen[value] = true
end
nil
end
# Expected O(n) time and O(n) auxiliary space.
raise unless first_duplicate([7, 2, 5, 2, 9]) == 2
raise unless first_duplicate([1, 2, 3]).nil?
Common Mistakes & Pitfalls
Counting only outer loops (miss nested each as O(n^2)), or calling sort O(n) (it's O(n log n)).
Check your understanding
Answer these without looking back at the article.
- Why are two loops not always O(n²)?
- What is the difference between expected and amortised complexity?
- Which Ruby collection methods can hide allocation or repeated scanning?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.