DSA SheetLesson · no judge

TIME AND SPACE COMPLEXITY / ONLINE JUDGE › TIME AND SPACE COMPLEXITY

Time Complexity Measures Growth, Not Stopwatch Seconds

Reading · 5 minQuiz · 5 questions2 code drills · run onlyGenerated by gpt-5.6-luna · Aug 25

A stopwatch measures one run, not time complexity

A linear search for 5 in [8, 3, 5, 1] visits the array from left to right and returns index 2 when it finds the target.

CPPThe search stops when it finds target 5 at index 2.
int arr[] = {8, 3, 5, 1};
int target = 5;
int index = -1;

for (int i = 0; i < 4; i++) {
    if (arr[i] == target) {
        index = i;
        break;
    }
}

If you time this execution, the stopwatch reports how long this run took on one particular computer. The measured duration can change with the hardware, programming language, compiler, and current system load. The same code can therefore take different numbers of seconds without changing the algorithm or the work its search performs.

CHECKPOINT 1Not answered

Which statement gives a machine-independent description of the search for 5 in [8, 3, 5, 1]?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The input size n is the scale that time complexity tracks

For this search, the input size n is the number of elements in the array. The array [8, 3, 5, 1] has four elements, so n = 4. The search happens to visit only the first three elements before stopping, but the input size still counts all four elements supplied to the algorithm.

Time complexity asks how the required work responds when n changes. The concrete trace remains [8, 3, 5, 1] with n = 4, so it gives one small observation. To describe the algorithm itself, you think about the same kind of search on arrays with different numbers of elements, rather than treating one measured running time as the whole answer.

Counting equality checks exposes the search's work

The condition array[i] == 5 is a basic operation for this search. At index 0, the condition checks 8 == 5 and gets false. At index 1, it checks 3 == 5 and gets false. At index 2, it checks 5 == 5 and gets true, so the search returns index 2 and stops.

INDEXEQUALITY CHECKRESULTSEARCH ACTION
08 == 5falseContinue to index 1
13 == 5falseContinue to index 2
25 == 5trueReturn index 2 and stop
The equality checks made by the search.

This search makes three equality checks before it stops. Counting that basic operation describes the work more reliably than elapsed seconds, because the count comes from the algorithm's steps rather than from the machine running them.

the linear search trace through [8, 3, 5, 1] for target 5Four adjacent array boxes contain 8, 3, 5, and 1 at indices 0, 1, 2, and 3. A bracket across all boxes says n = 4. The search checks 8 == 5 at index 0 and gets false, checks 3 == 5 at index 1 and gets false, then checks 5 == 5 at index 2 and gets true. A stop marker follows index 2, and index 3 is not visited.STOP83518 == 5false3 == 5false5 == 5truen = 40123
The search performs three equality checks before it finds 5.
CHECKPOINT 2Not answered

How many equality checks are made before target 5 is found in [8, 3, 5, 1]?

if (arr[i] == 5)

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

Time complexity describes growth, not an exact duration

Time complexity connects the input size n to the amount of work an algorithm requires. For this search, the counted work is represented by equality checks as the array size changes. The trace with n = 4 makes three checks, but time complexity is about the pattern of work across changing input sizes, not only this one trace.

This view supports machine-independent reasoning: you can discuss how the search's work responds to a larger input without claiming that it will take a particular number of seconds. Time complexity does not predict the exact duration of this search on your computer, because elapsed time still depends on the hardware, language, compiler, and current system load.

Next part · Quiz