Algorithms for Coding Interviews in C#/

...

/

Example: Measuring Time Complexity—Single Loop

Example: Measuring Time Complexity—Single Loop

Learn how to compute the running time complexity of an algorithm that involves loops.

We'll cover the following...

Let’s now calculate the running time complexity of a more complex program. We will split the code into individual operations and then compute the number of iterations.

A simple for loop of size n

Here is an example of a simple loop of size n:

Press + to interact
int n = 10; // Just as an example, 'n' can be anything
int sum = 0;
for (int i = 0; i < n; i++)
{
    sum += 1;
}
System.Console.WriteLine(sum);

Operation

Number of Executions

n = 10

11

sum = 0

11

for (int i = 0; i < n; i++)

11

i=0

11

i=1

11

i=2

11

...

i=n-1

11

sum+=1

nn

System.Console.WriteLine(sum)

11

Note: While for (int i = 0; i < n; i++) executes only once, its execution cost is nn ...