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

Example 1: Measuring Time Complexity of a Single Loop Algorithm

Explore how to accurately measure the time complexity of a single loop algorithm in C# by counting primitive operations such as initialization, increments, and tests. Understand how these operations contribute to the overall running time and learn to express it as a function of input size n.

We'll cover the following...

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

A for Loop with n iterations

Now, consider what happens when a loop is involved. Consider the following C# program:

C#
using System;
namespace Chapter_1
{
    class Example1
    {
        static void Main(string[] args)
        {
            int n = 10;
            int sum = 0;
            for (int i = 0; i < n; i++)
                sum += 2;
            Console.Write(sum);
            return;
        }
    }
}

Count the number of primitive operations in the above program. Skip the non-executable lines, and go to lines 8 and 9 where variable initializations are taking place. They account for one primitive operation each.

Line 10 is a loop statement. To count the number of primitive operations on that line, you must dissect it into its constituents: the initialization, the increment, and the test. The initialization occurs only once, and it 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 ...