One Pass Over the Data
O(n) means linear time: the work grows in step with the input. Twice the elements, twice the steps.
In TypeScript, linear time usually looks like one for loop over an array or a Map. Every algorithm that must at least look at every element — summing, counting, searching an unsorted array — cannot be faster than O(n).
Linear is a good complexity. Millions of elements are no problem for one pass.
Linear Search
When the array is not sorted, the only way to find a value is to check the elements one by one, from the start. That is a linear search.
In the worst case — the value is last, or not there at all — the loop visits all n elements. That worst case is what O(n) describes.
Find a value and its position
The loop checks "one", "two", "three" before it reaches "four" — 4 steps for a match at index 3. break stops the loop as soon as the value is found.
Output: TypeScript file and captured output
const words = ["one", "two", "three", "four", "five"]
let steps = 0
for (let i = 0; i < words.length; i++) {
steps++
if (words[i] === "four") {
console.log("found at index", i, "after", steps, "steps")
break
}
}
Visiting Every Element
Many everyday tasks are one pass over the whole array: add all values, keep the biggest one seen so far, count the elements that pass a test. Each element is touched exactly once, so all of them are O(n).
Doing two or three of these passes in a row is still linear — O(2n) and O(3n) collapse to O(n).
Sum all elements
The loop adds every element to sum. 8 elements, 8 additions — the classic one-pass shape.
Output: TypeScript file and captured output
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let sum = 0
for (const n of nums) {
sum += n
}
console.log("sum of", nums.length, "elements:", sum)
Find the biggest value
biggest starts as the first element; every other element that is bigger replaces it. After one pass the biggest value, 9, remains.
Output: TypeScript file and captured output
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let biggest = nums[0]
for (let i = 1; i < nums.length; i++) {
if (nums[i] > biggest) {
biggest = nums[i]
}
}
console.log("biggest value:", biggest)
Count the matches
The loop tests every word with w.length > 3 and counts the hits. Three words are longer than 3 letters.
Output: TypeScript file and captured output
const words = ["one", "two", "three", "four", "five"]
let count = 0
for (const w of words) {
if (w.length > 3) {
count++
}
}
console.log(count, "words are longer than 3 letters")