Interesting Time Complexity Questions in C++

Problem Statement 1

Our task will analyze the following code or function to calculate the time complexity to know if this code is suitable for large input sizes depending on which category it will fall into. Once we analyze this time complexity question, we will again analyze this statement with a different approach.

void fun1(int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < n; j+=i)
		{
			cout << i << " " << j << endl;
		}
	}
}

Code:

#include <iostream>
using namespace std;

void fun1(int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < n; j+=i)
		{
			cout << i << " " << j << endl;
		}
	}
}

// Main function

int main()
{
	fun1(10);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Analysis

In the time complexity question, the inner loop of fun1() will run (n/i) times for each value of i. 

For i=1,

the inner loop will run (n/1) times; 

for i=2,

the inner loop will run (n/2) times; 

……………………………

For i=n,

the inner loop will run (n/n) times; 

So, the total number of operations in the function

=(n/1 + n/2 + n/3 + n/4 + n/5………… + n/n)

=n(1/1 + 1/2 + 1/3 + 1/4 + 1/5………… + n/n)
 

Value of (1/1 + 1/2 + 1/3 + 1/4 + 1/5………… + n/n) expression can be approximated as (log n)

So, the total number of operations= n(log n).

The function's time complexity in Big O-notation is O(nlog n).

Read More - Time Complexity of Sorting Algorithms

Problem Statement 2

Now we will again try the observe the above problem, but this time the inner loop will run until log(i) times so that we can observe both statements and decide which code is better depending on the time complexity.

void fun2(int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < log(i); j++)
		{
			cout << i << " " << j << endl;
		}
	}
}

Code:

#include <bits/stdc++.h>
using namespace std;

void fun2(int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < log(i); j++)
		{
			cout << i << " " << j << endl;
		}
	}
}

// Main function

int main()
{
	fun2(10);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Analysis

In the time complexity question, the inner loop will run log(i) times for each value of i. 

For i=1,

the inner loop will run log(1) times; 

for i=2,

the inner loop will run log(2) times; 

……………………………

For i=n,

the inner loop will run log(n) times; 

So, the total number of operations in the function

=(log(1)  + log(2)  + log(3) + log(4) + log(5) ………… +log(n))

=log(1*2*3*..........*n) ( because log m*n = log m + log n )

=log(n!)

The time complexity of the above function in terms of Big O-notation is O(log n!).
 

Now we have analyzed the time complexity question with two different approaches, and we can observe that approach 1 is more suitable because in that, we got O(nlogn) complexity, and in the second approach, we got O(log n!).

Must Read Lower Bound in C++

Frequently Asked Questions

What is the Big O-notation?

Big O-notation is one of the asymptotic notations in time complexity that we use to measure the efficiency of an algorithm in worst-case analysis.

Are running time and time complexity the same?

Time complexity is a theoretical concept that gives us an idea of how efficient the algorithm is with respect to the input size, where the running time of an algorithm or program depends on various factors like the machine's computational power, input size, and many other factors.

What are asymptotic notations?

Asymptotic notations are the mathematical notation we use to label an algorithm after calculating the time complexity for the input size. Big-O, Big-Omega, and Big-Theta are the types of asymptotic notations.

What are Big-Omega Ω-Notation and big-Theta Θ-Notation?

Big-Omega Ω-Notation is the asymptotic lower bound of an algorithm, and big-Theta Θ-Notation is the asymptotic tight bound (i.e., average-case time complexity) of an algorithm.

What is the best time complexity in the worst case?

The O(1) is the best average time because the input size does not affect the algorithm.

Conclusion

This article has covered an interesting time complexity question. We have shown the approach of time complexity analysis of a program. We have also discussed in brief the time complexity and its notations.

To learn more about time complexity, check out the following articles:

• Time Complexity of building a heap
• Time and space complexity of STL containers
• Time and Space Complexity of Non-Linear Data Structures
• Time & Space Complexity of Searching Algorithms
   

To learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.