15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 1 of 12 in the free DSA Basics course · 6 lessons
You will learn to analyze small algorithms before considering implementation details. By the end, you will be able to:
n,Describe how an algorithm's work and extra memory change as the input becomes larger instead of timing code with a stopwatch.
None.
You only need to be comfortable reading basic pseudocode with variables, arrays, comparisons, loops, and return.
Use linear search to find a target in an array:
1for i from 0 to items.length - 1:
2 if items[i] == target:
3 return i
4return -1For items = [4, 1, 7] and target = 7:
i = 0: inspect items[0] = 4. This is comparison 1. The target is not found.i = 1: inspect items[1] = 1. This is comparison 2. The target is not found.i = 2: inspect items[2] = 7. This is comparison 3. The target is found, so return index 2.Let n be the number of items. Linear search may perform from 1 comparison up to n comparisons, depending on where the target appears or whether it is absent. It uses a fixed number of variables, such as i, so its auxiliary space stays constant even when the array grows.
The running example connects operation counts, asymptotic notation, common classes, loop structure, and input-dependent cases.
Time Complexity Concepts defines a measurable model of algorithm work before you compare growth rates. Define n and count a chosen operation, such as the equality comparison in linear search.
Space Complexity Concepts separates memory use from running time. After counting search comparisons, identify the fixed extra variables the search uses and distinguish them from the input array.
Asymptotic Notations gives a formal way to describe growth while ignoring implementation-dependent constants and lower-order terms. Given an operation-count function, state upper, lower, and tight growth bounds.
Common Complexity Classes names the forms used in later analyses: constant, logarithmic, linear, linearithmic, and quadratic growth.
Loop Analysis applies operation counting and asymptotic simplification to concrete control flow. Derive costs from loop structure.
Performance Case Analysis adds explicit input-dependent conditions to loop analysis. Linear search provides best-case, worst-case, and expected-case behavior.
Start by deciding what work to count. In the running example, comparisons are a useful basic operation because each array element may need to be checked.
Memory needs a separate analysis. A search can take more comparisons as n grows while still using only constant auxiliary space. Time and auxiliary space measure different resources.
After you can write a count such as “at most n comparisons,” asymptotic notation gives that statement a standard form. Linear search has an upper bound of O(n) comparisons and, for an unsuccessful search, also has a lower bound of Ω(n), so that condition has Θ(n) comparison growth.
Common classes help compare those results. A single pass through an array is typically linear. Two consecutive full passes are still linear because their costs add: n + n = 2n, which simplifies to O(n). Independent nested full loops multiply their iteration counts, producing about n² work. A loop that repeatedly halves a value reaches 1 after about log n iterations.
A class alone does not explain every run. For linear search:
n comparisons when the target is last or absent.n positions, the expected number of comparisons is (n + 1) / 2.Each case label requires its condition. “Expected case” is incomplete until the assumed input distribution is stated.
n, choose one basic operation, and trace a few concrete inputs.3n + 2, n² + n, and 5 into asymptotic bounds.O(1), O(log n), O(n), O(n log n), and O(n²).