Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C++

Example: Measuring Time Complexity of a Single Loop Algorithm

Explore how to calculate the time complexity of a C++ algorithm with a single loop by counting primitive operations including initialization, increments, and tests. Understand how these operations contribute to the overall time complexity expressed in Big O notation. This lesson helps you dissect loop components to analyze running time precisely.

We'll cover the following...

In the previous lesson, we calculated the time complexity of the algorithm implemented in a simple C++ program.

A For Loop With n Iterations #

Now, 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 ...