Different Levels of Complexity

Different Levels of Complexity

In this article, we are going to discuss different levels of complexity in terms of big O. When we talk about code complexity we have different levels of complexity for the algorithms.

complexity level

Here, The image shows the graph for the complexity level from low to high. The first level lists O(n). When we talk about big O. We will represent the notation as O. And next level is O(log n) and the next levels O(n) and next higher level is O(n log n) and next is O(n2) and the next one is O(2n).

In this graph, I am referring to all the levels of complexity in terms of big O. Because we are not going to concentrate on the best case and average case scenarios. Our ultimate aim is to take the worst-case scenarios and work with them in the best way.

I will give an example of these levels of complexities. So that you will get a clear idea about these complexities.

Constant Time Complexity: O(1)

So the complexity of O(1) means it’s one step to execute.

For example A = B + C or C = 1 + 8 something like this.

Logarithmic Time Complexity: O(log n)

The next level of complexity is O(log n) is basically time goes up linearly while the end goes up exponentially.

So if the program takes 1 second to compute 10 elements it will take two seconds to compute a hundred elements and it will take three seconds to compute a thousand elements and so on. i.e 101 = 10, 102=100 and 103=1000.

Take this example this block of code will act based on log base 2. The for loop multiplies the current value of i by 2.

for(int i = 1; i <= n; i = i*2){
	System.out.println("hello");
}

So it goes from 1 to 2, 2 to 4, 4 to 6, 6 to 8, 8 to 16, and 16 to 32 like that. Because every time we are multiplying the i value with 2. In this block of code just think we passing the value as 8.

Initially, the i value will be 1 and after the next iteration, it’s 1*2 which is equal to 2. For the next iteration, 2*2 which is equal to 4, and for the next iteration i will be 8.

So this “hello” prints for the 4 times. If I increment the i value by 1, this loop will execute 8 times. But it’s not the case here.

Here, we are doubling the value of each iteration. So this block of code complexity is O(log n).

I will do this for log base 3. Then the code will be like.

for(int i = 1; i <= n; i=i*3){
	System.out.println("hello");
}

Here, i value goes from 1 to 3, 3 to 9, and 9 to 27 like that.

So “hello” will print two times. Because when this loop executes for the second time i value will be 9. So it will be exit from the loop because we have given and value as 8.

Linear Time Complexity: O(n)

for(int i = 1; i <= n; i++){
	System.out.println("hello");
}

In the above block of code, i value is increasing by 1. If we post n = 8 here, this loop will execute for 8 times. If n is 100 then it will be 100 times.

So complexity for this code is O(n).

Logarithmic Time Complexity: O(n log n)

for(int i = 0; i < n; i++){
	for(int j = 1; j < n; j = j*2){
		System.out.println("hello");	
	}
}

See this piece of code. This for loop is inside of the another for loop. So the first for loop will execute for n times. And inside that, the other for loop will execute for log(n) times. Because we are incrementing the j value with log base 2.

So its complexity is log(n) and the first loop complexity is n time. So its complexity is n times of log(n). Which is equal to O(n log n).

Quadratic Time Complexity: O(n²)

The next level of complexity is O(n2). Which is for loop is inside of another for loop.

See this example.

for(int i = 0; i < n; i++){
	for(int j = 1; j < n; j++){
		System.out.println("hello");	
	}
}

This for loop is inside of another for loop. This second for loop complexity is n and it is present inside the first for loop. And its complexity is also n. Because we are incrementing the i value by 1. So n times of n. i.e n*n which is equal to n2 complexity.

Exponential Time Complexity: O(2n)

Different levels of complexities in terms of big O. When we talk about code complexity We will have a different level of complexity for the algorithms.

int fibonacci(int number){
	if (number <= 1) return number;

	return fibonacci (number - 2) + fibonacci (number - 1)
}

The Fibonacci method will call for two times and recursively it will call for multiple times. So the complexity is 2n.

Let’s take that you are going to sort some numbers from the given array. We already have predefined algorithms for sorting problems. i.e bubble sort, insertion sort, selection sort, quicksort and merge sort,

If you use bubble sort, insertion sort, selection sort, quick sort your code complexity will be O(n2). For merge sort, it’s O(n log n).

nv-author-image

Kalpesh Khairnar

Hello Everyone, I'm Kalpesh. Energetic and passionate college student with the ability to work with open-source technologies. I spend most of my time in programming, blogging and helping other programming geeks.

Leave a Reply

Your email address will not be published. Required fields are marked *