Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Example: Measuring Time Complexity of a Single Loop Algorithm

Explore how to measure time complexity in C++ single loop algorithms by counting primitive operations such as initialization, increment, and comparison. Understand how these operations accumulate through iterations and affect the overall time complexity calculation. This lesson helps you analyze runtime efficiency by breaking down the components of a loop, preparing you to evaluate similar algorithms accurately.

We'll cover the following...

A For Loop With n Iterations

Let’s consider what happens when a loop is involved. Consider the following C++ program::

C++
#include <iostream>
using namespace std;
int main(){
  int n = 10;
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += 2;
  cout << sum;
  return 0;
}

Let’s count the number of primitive operations in the above program. We skip the non-executable lines and come to lines 4 and 5 where variable initializations are taking place, which account for one primitive operation, each.

Line 6 is a loop statement. To count the number of primitive operations on that line, we must dissect it into its constituents: the initialization, the increment, and the test. The initialization occurs only once and is counted as one primitive operation. The increment (i++i++) operation must read the current value of variable ii, add 11 to it and store the result back in variable ii. That’s three primitive operations. The test operation (i<ni < n) must read the current value of the variables ...