DSA
Category

Cost

These articles name how the number of steps changes as the input grows, and how much extra memory an algorithm needs. They cover Big O, constant, logarithmic, linear, linearithmic, and quadratic time, loop invariants, amortized cost, and trading space for time. A lesson that writes O(n) or O(n²) is pointing at one of these.

  1. What Is Big O? How Algorithm Cost Grows as Input Grows

    Big O describes how the number of steps grows as the input grows, ignoring constant factors and one machine's speed. An O(n) scan doubles when the input doubles; an O(n²) pair of loops grows much faster.

  2. What Does O(1) Mean? Constant-Time Work That Stays Flat

    O(1) means work stays flat as input grows. Reading a known array slot is constant time; dynamic-array append is O(1) amortized across a sequence of pushes.

  3. What Is Linear Time O(n)? One Pass and Linear Search

    O(n) means one pass over the input: twice the data, about twice the work. Linear search is that scan, and it looks at every element when the target is missing.

  4. What Is O(n²) Quadratic Time? Nested Loops and Pairs

    O(n²) is the cost of looking at the other elements for each element, usually a loop inside a loop. Ten items are a small triangle of comparisons; a thousand items are on the order of a million.

  5. What Is a Loop Invariant? Proving Each Iteration Is Correct

    A loop invariant is a statement that is true before or after every iteration. Establish it before the loop, preserve it through each update, and use it at termination to explain why the result is correct.

  6. What Is Amortized Analysis? Cost Across a Sequence of Operations

    Amortized analysis bounds the total cost of a sequence and divides that cost across its operations. It explains why an occasional O(n) dynamic-array resize can coexist with O(1) amortized append.

  7. What Is O(log n)? Logarithmic Time and Binary Search

    O(log n) means each step throws away a fraction of what remains. Binary search on a million sorted values is about twenty comparisons, and a balanced tree has about that many levels.

  8. What Is O(n log n)? Linearithmic Time and Sorting

    O(n log n) is linear work repeated about log n times, which is the usual cost of a good sort. You can sometimes beat it when the input is already ordered, as with sorted squares.

  9. What Is the Space-for-Time Tradeoff in Algorithms?

    Spending extra memory can turn a scan into a lookup. The extra space is part of the cost: say O(n) time and O(n) extra space, not the time on its own.

  10. What Is Auxiliary Space? Measuring an Algorithm's Extra Memory

    Auxiliary space is the memory an algorithm uses beyond its input. A few counters are O(1), a table that grows with the input is O(n), and recursive call-stack frames count too.

  11. How Do You Enumerate Every Index Pair Exactly Once?

    Pair enumeration uses i < j to exclude self-pairs and reversed duplicates. Its triangular iteration count explains the quadratic cost.