What is meant by the Time Complexity of an Algorithm?
Now, the question arises if time complexity is not the actual time required to execute the code, then what is it?
The answer is:
Instead of measuring actual time required in executing each statement in the code, Time Complexity considers how many times each statement executes.
Example 1: Consider the below simple code to print Hello World
#include <iostream>
using namespace std;
int main()
{
cout << "Hello World";
return 0;
}
// This code is contributed by vikash36905.
#include <stdio.h>
int main()
{
printf("Hello World");
return 0;
}
import java.io.*;
class GFG {
public static void main(String[] args)
{
System.out.print("Hello World");
}
}
// This code is contributed by vikash36905.
print("Hello World")
# This code is contributed by akashish__
using System;
public class GFG{
static public void Main (){
// Code
Console.WriteLine("Hello World");
}
}
// This code is contributed by lokesh
console.log("Hello World")
// This code is contributed by nilha72xi.
Output
Hello World
Time Complexity: In the above code “Hello World” is printed only once on the screen.
So, the time complexity is constant: O(1) i.e. every time a constant amount of time is required to execute code, no matter which operating system or which machine configurations you are using.
Auxiliary Space: O(1)
Example 2:
#include <iostream>
using namespace std;
int main()
{
int i, n = 8;
for (i = 1; i <= n; i++) {
cout << "Hello World !!!\n";
}
return 0;
}
// This code is contributed by vikash36905.
#include <stdio.h>
void main()
{
int i, n = 8;
for (i = 1; i <= n; i++) {
printf("Hello World !!!\n");
}
}
class GFG {
public static void main(String[] args)
{
int i, n = 8;
for (i = 1; i <= n; i++) {
System.out.printf("Hello World !!!\n");
}
}
}
// This code is contributed by Rajput-Ji
# Python code
n = 8
for i in range(1, n + 1):
print("Hello World !!!")
# This code is contributed by lokesh
using System;
public class GFG {
public static void Main(String[] args)
{
int i, n = 8;
for (i = 1; i <= n; i++) {
Console.Write("Hello World !!!\n");
}
}
}
// This code contributed by Rajput-Ji
let i, n = 8;
for (i = 1; i <= n; i++) {
console.log("Hello World !!!");
}
Output
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!
Time Complexity: In the above code “Hello World !!!” is printed only n times on the screen, as the value of n can change.
So, the time complexity is linear: O(n) i.e. every time, a linear amount of time is required to execute code.
Auxiliary Space: O(1)
Example 3:
#include <iostream>
using namespace std;
int main()
{
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
cout << "Hello World !!!\n";
}
return 0;
}
// This code is contributed by Suruchi Kumari
#include <stdio.h>
void main()
{
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
printf("Hello World !!!\n");
}
}
// This code is contributed by Suruchi Kumari
class GFG {
public static void main(String[] args)
{
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
System.out.println("Hello World !!!");
}
}
}
// This code is contributed by Suruchi Kumari
n = 8
# for (i = 1; i <= n; i=i*2) {
for i in range(1, n+1, 2):
print("Hello World !!!")
# This code is contributed by akashish__
using System;
public class GFG{
static public void Main (){
// Code
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
Console.Write("Hello World !!!\n");
}
}
}
// This code is contributed by lokeshmvs21.
for (i = 1; i <= 8; i=i*2) {
console.log("Hello World !!!");
}
// This code is contributed by nilha7xi.
Output
Hello World !!! Hello World !!! Hello World !!! Hello World !!!
Time Complexity: O(log2(n))
Auxiliary Space: O(1)
Example 4:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int i, n = 8;
for (i = 2; i <= n; i=pow(i,2)) {
cout << "Hello World !!!\n";
}
return 0;
}
// This code is contributed by Suruchi Kumari
#include <stdio.h>
#include <math.h>
void main()
{
int i, n = 8;
for (i = 2; i <= n; i=pow(i,2)) {
printf("Hello World !!!\n");
}
}
// This code is contributed by Suruchi Kumari
import java.lang.Math;
class GFG {
public static void main(String args[]){
int i, n = 8;
for (i = 2; i <= n; i=(int)Math.pow(i,2)) {
System.out.println("Hello World !!!");
}
}
}
n = 8
i = 2
for j in range(2,n+1):
if(i >= n):
break
print("Hello World !!!")
i *= i
# This code is contributed by akashish__
using System;
using System.Collections.Generic;
public class GFG {
static public void Main()
{
int i, n = 8;
for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) {
Console.WriteLine("Hello World !!!");
}
}
}
// This code is contributed by akashish__
for (let i = 2; i <= 8; i=Math.pow(i,2)) {
console.log("Hello World !!!");
}
// This code is contributed by nilha7xi.
Output
Hello World !!! Hello World !!!
Time Complexity: O(log(log n))
Auxiliary Space: O(1)
Understanding Time Complexity with Simple Examples
A lot of students get confused while understanding the concept of time complexity, but in this article, we will explain it with a very simple example.
Q. Imagine a classroom of 100 students in which you gave your pen to one person. You have to find that pen without knowing to whom you gave it.
Here are some ways to find the pen and what the O order is.
- O(n2): You go and ask the first person in the class if he has the pen. Also, you ask this person about the other 99 people in the classroom if they have that pen and so on,
This is what we call O(n2). - O(n): Going and asking each student individually is O(N).
- O(log n): Now I divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).
I might need to do:
- The O(n2) searches if only one student knows on which student the pen is hidden.
- The O(n) if one student had the pen and only they knew it.
- The O(log n) search if all the students knew, but would only tell me if I guessed the right side.
The above O -> is called Big – Oh which is an asymptotic notation. There are other asymptotic notations like theta and Omega.
NOTE: We are interested in the rate of growth over time with respect to the inputs taken during the program execution.
Contact Us