8. Time Complexity
We have already seen many examples of different kind of data structures and algorithms. We have also found out that to implement such algorithms, we do not have to go through low-level plumbing. Any stable good programming language provides many libraries to avoid such low-level plumbing and different types of algorithms, such as sorting, shuffling, or searching can be done through them.
We have also found out another important fact that tells us about the relationship between algorithms and discrete mathematics. Data structures are discrete structures and hence, the algorithms are all about discrete structures.
Let us consider a simple Java program, where we iterate over two loops at the same time. These outer and inner loops are connected with each other and they finally give us an output.
1 //code 8.1
2 package fun.sanjibsinha;
3
4 public class Main {
5
6 static int i, j, totalOne, totalTwo;
7
8 public static void main(String[] args) {
9
10 for (i = 0; i <= 5; i++){
11 totalOne += i;
12 System.out.print("i = " + i);
13 System.out.println("--------");
14 for (j = 0; j <= 5; j++){
15 totalTwo += j;
16 System.out.println("j = " + j);
17 }
18 }
19 System.out.println("The total of outer loop: " + totalOne);
20 System.out.println("The total of inner loop: " + totalTwo);
21 }
22 }
And from this very simple program, we get an output like the following:
1 //output of 8.1
2 i = 0--------
3 j = 0
4 j = 1
5 j = 2
6 j = 3
7 j = 4
8 j = 5
9 i = 1--------
10 j = 0
11 j = 1
12 j = 2
13 j = 3
14 j = 4
15 j = 5
16 i = 2--------
17 j = 0
18 j = 1
19 j = 2
20 j = 3
21 j = 4
22 j = 5
23 i = 3--------
24 j = 0
25 j = 1
26 j = 2
27 j = 3
28 j = 4
29 j = 5
30 i = 4--------
31 j = 0
32 j = 1
33 j = 2
34 j = 3
35 j = 4
36 j = 5
37 i = 5--------
38 j = 0
39 j = 1
40 j = 2
41 j = 3
42 j = 4
43 j = 5
44 The total of outer loop: 15
45 The total of inner loop: 90
You have probably noticed that it is a simple algorithm of finding the total of inner loop and the outer loop.
However, to do that, we need to jump sequentially; each iteration has taken place within a space of discrete data structure.
Any problem has one or more possible solutions. Suppose, we were asked to find the total of the one loop only; we should change the above code to the following code:
1 //code 8.2
2 package fun.sanjibsinha;
3
4 public class Main {
5
6 static int i, j, totalOne, totalTwo;
7
8 public static void main(String[] args) {
9
10 for (i = 0; i <= 5; i++){
11 totalOne += i;
12 System.out.print("i = " + i);
13 System.out.println("--------");
14 /*
15 for (j = 0; j <= 5; j++){
16 totalTwo += j;
17 System.out.println("j = " + j + ", ");
18 }
19 */
20 }
21 System.out.println("The total of loop: " + totalOne);
22 // System.out.println("The total of outer loop: " + totalTwo);
23 }
24 }
Now, in the changed circumstance, we will come up with this output:
1 //output of 8.2
2 i = 0--------
3 i = 1--------
4 i = 2--------
5 i = 3--------
6 i = 4--------
7 i = 5--------
8 The total of loop: 15
Now we can also solve this problem another way. By calling the function recursively, we can also solve the same problem. Our problem was, how we could get the total of a series of positive integers that starts from 0 and ends at 5.
It looks like this: total = 0 + 1 + 2 + 3 + 4 + 5; here the end point was chosen as 5. The value of total is 15.
We could have taken the user input and get the total of any big positive integer. Manually it is easy to get the total of a small series. But consider a case, where user gives us an input like 10 to the 6. Now, manually it is not possible to add all the numbers from 0 to that number.
It becomes cumbersome.
Therefore our first algorithm was based on using looping. It easily adds all the numbers, whatever be the end number.
As we have said, any problem might have one or more solutions. Here we can solve the same problem, recursive way.
1 //code 8.3
2 package fun.sanjibsinha;
3
4 public class Main {
5
6 static int total;
7
8 static int getTotal(int i){
9 if (i != 0){
10 total = i + getTotal(i - 1);
11 return total;
12 } else {
13 return 0;
14 }
15 }
16
17 public static void main(String[] args) {
18
19 System.out.println("Total : " + getTotal(5));
20
21 }
22 }
And we get the same output:
1 //output of 8.3
2 Total : 15
In the above case, the same jumping of iteration occurs through a discrete structure, but in a different way. It starts from a discrete positive integer 5, and the addition process goes on until we reach the base number by calling the function recursively.
Now we have found that this problem has two solutions. Question is which is desirable? Which algorithm is better than the other?
Here comes the question of time complexity.
Time-Complexity has nothing to do with the execution time.
But it has many things to do with the algorithm. Time-Complexity talks all about the better algorithm. A better algorithm always takes less time to reach the desirable discrete element (here output of a total).
Here we have to iterate over a series of positive integers,to reach our desirable goal. If we could have reached in one iteration, that would be the best algorithm, no doubt.
But it is Utopian.
On the contrary, the worst case will take us to an iteration, that has to traverse each element for an indefinite period of time. In like manner, you may imagine a situation where user gives an input to find whether the integer is prime or not. There are several algorithms to test a number whether it is prime or not. Although there will be one algorithm that is better than other, and takes less time to give you the output. It depends entirely on the size of the input. For a real big integer, one algorithm might take several minutes to complete the operation and for another algorithm, it finishes the operation in a few seconds.
Before trying to understand Time-Complexity, we should remember that actual time requires to execute code is machine dependent; another key thing is network load. But the Time-Complexity has nothing to do with your machine configuration. It is all about better algorithm. That is why, whenever the terms data structures and algorithms appear, time-complexity comes with them.
In this chapter, we will try to understand how time-complexity works. What does the term Big O notation stand for? But before that, we need to understand what does ‘order of n’ mean?
Order of n, or O(n)
Let us implement an algorithm that will check whether the number or ‘n’ is prime or not. We know that a prime number is divided by only two numbers, 1 and the number itself and it has no remainder. Consider a prime number 11, it has only two factors 1, and 11. If we divide 11 by 1 and 11, we have no remainders. That is the most basic definition.
Therefore, using a normal looping construct, we can try to check whether that number is prime or not. We can write our algorithm in natural language, this way:
1 for each number where integer i starts from 2 to (n - 1)
2 if n % i == 0, then n is not prime
3 else n is prime
We can test this algorithm by using a small positive integer like 11. In that case, if we iterate from 2 to (11 – 1), we will see that between 2 to 10, there is no integer that can divide 11 with no remainder. Therefore, 11 is prime. When the value of n is small, our algorithm does not take much time. In fact, that time may appear negligible. Suppose for each iteration, it takes one millisecond or ms. This fraction of second stands for 10 to the power minus 3, that is, if you divide 1 second by 1000, then you get one millisecond.
By the way, as a student of computer science student we should know that one microsecond is 10 to the power minus 6, one nanosecond is 10 to the power of minus 9 and one picosecond is 10 to the power minus 12.
Now, let us assume that each iteration takes one microsecond. When the number of iteration is small, it does take mush time. However, with the increase of iteration, this time also increases. Instead of 11, we want to check a value like 1000003, it will iterate more than one million times. Now our algorithm appears to crumble. Because our algorithm will take huge time to finish the process of iteration.
We can transport this natural language algorithm to a Java code.
1 //code 8.4
2
3 package fun.sanjibsinha.timecomplexity;
4
5 import java.util.Scanner;
6
7 public class TimeOne {
8
9 static long userInput;
10
11 public static void main(String[] args) {
12 Scanner sc = new Scanner(System.in);
13 System.out.println("Enter a positive integer to test prime or not: ");
14 userInput = sc.nextInt();
15
16 for (long i = 2; i < (userInput - 1); i++){
17 if (userInput % i == 0){
18 System.out.println(userInput + " is not prime.");
19 } else {
20 System.out.println(userInput + " is prime.");
21 }
22 }
23 }
24 }
We are not going to run this code; it is just for an example of time-complexity. In the above code you can guess that to reach our goal we need to iterate ‘n’ number of times. Here ‘n’ is user’s input. It is called ‘order of n’ or O(n). As the value of ‘n’ starts increasing, our algorithm starts crumbling. For a value like 10 to power 6 plus 3, it takes huge to time and it simply goes out of our hands.
Therefore, we have to search for a better algorithm to solve the same problem.
Let us take the user’s input and instead of iterating over the whole range of that number, we can calculate the square root of that user’s input. After that we can iterate up to that value.
It serves our purpose, and at the same time, shortens the length of iteration in a great way. Let us write the code in Java.
1 //code 8.5
2
3 package fun.sanjibsinha.timecomplexity;
4
5 import java.util.Scanner;
6
7 public class TimeTwo {
8 static double userInput;
9
10 public static void main(String[] args) {
11 Scanner sc = new Scanner(System.in);
12 System.out.println("Enter a positive integer to test prime or not: ");
13 userInput = sc.nextInt();
14
15 // 10 to the power 6 + 3 = 1000003
16 for (long i = 2; i < (Math.sqrt(userInput)); i++){
17 if (userInput % i == 0){
18 System.out.println(userInput + " is not prime.");
19 } else {
20 System.out.println(userInput + " is prime.");
21 }
22 }
23 }
24
25 }
If we have a user’s input like 1000003, our algorithm allows us not to iterate more than 1 million times. On the contrary, it allows us to iterate in and around 1000 times.
We write another short Java code to find the square root of any number.
1 //code 8.6
2
3 package fun.sanjibsinha.timecomplexity;
4
5 public class TestClass {
6
7 public static void main(String[] args) {
8
9 System.out.println(Math.sqrt(1000003));
10 //1000.001499998875
11 }
12 }
13
14
15 //output of 8.6
16
17 Square root of 10 to the power of 6 plus 3 is: 1000.001499998875
In the above code we can clearly see that the square root of 1000003.
Let us go back to the code 8.5, where we have successfully shortened the length of iteration by calculating the square root of user’s input. Reducing the length of iteration means the algorithm takes much less time. Now the running time of our code is not ‘order of m’, but ‘order of square root of n’; it means O(square root of n). It is quite evident that code 8.5 represents much better algorithm than code 8.4 to solve the same problem. Why so? Because, it solves the large test cases in acceptable time. Better algorithm is necessary for better performance.
Here the running time of the program depends on the user’s input; and, user’s input represents the growth of time which exerts influence on the running time.
As a conclusion to this section, we can say that time-complexity only cares about the ‘input’. It also cares about the algorithm that tackles the ‘input’ in a better way.
Moreover, time-complexity does not care about the machine’s hardware configuration. Whether the machine is single processor or multi processor does not matter. What is the network load, is unimportant. The time-complexity really does not care about 32 bit or 64 bit.
Input is the key word for time-complexity. Nothing else.
In the above examples, we have inputs like single integer. It could have been an array, a data structure; is not it? Now, again, we come to the point of the data structures, and algorithms. And, of course, now we also understand how time-complexity is related to them.
Big O Notation
We have already seen how through order of ‘n’, or ‘input’, we can represent any algorithm. Consider the code 8.4, where we have to iterate over one million times if ‘n’ is 1000003. Therefore, the O(n) is the worst case scenario. Any algorithm could not be worse than that O(n).
Big O notation is the most convenient way to express the worst-case scenario for an algorithm. Compare code 8.5 with the previous code 8.4. In code 8.5, the Big O notation is like this: O(square root of n). This algorithm could not be worse than anything. Now, comparing these two worst case scenarios, we can safely tell that the algorithm of code 8.5 is better than code 8.4.
If you are still confused with the definition, do not worry. Everything takes time. The concept of time-complexity is related to algorithm. More you practice,you will be able to get your head around this topic.
Let us try to call back the second code snippet of this chapter. The code 8.2 looks like this:
1 package fun.sanjibsinha;
2
3 public class Main {
4 public static void main(String[] args) {
5 int totalOne = 0;
6 for (i = 0; i <= 5; i++){
7 totalOne += i;
8 }
9 System.out.println("The total of loop: " + totalOne);
10 }
11 }
For brevity we have trimmed the code omitting the commented parts. When we have declared the variable ‘totalOne’ to 0, the constant is 1 and the time is also 1. In the next step, the first line of the ‘for loop’ tells us about two things. First, the constant is more than one, and the same rule applies for the time.
In the next line the algorithm keeps adding the value of iteration for ‘n’ number of times. Therefore, we have two constants, but the time equals ‘n’.
The last line gives us the output. The constant is 1, and the time is also 1.
When we add them up, we get O(n). It happens so, because while summing it up, we remove all the constants.
However, for the code 5.1, where we have used nested loop to get the total of inner loop, this order of ‘n’ changes to (n * n), that is n squared. Therefore, the Big O notation or the worst case scenario of that algorithm is O(n2). Although in that code, we have total of the outer loop also. That means, we have O(n) at the same breath. Since there are consecutive statements, we count the statement with maximum complexity, that is O(n2).
We have got an initial idea of how Big O notation works, and what principles govern it. Many common algorithms we use very often, use the above Big O notation O(n^2). Common algorithms, such as bubble sort, selection sort and insertion sort takes the above Big O notation.
There are many other Big O notations that are related to different types of algorithms. The idea of time-complexity rests on finding the better algorithm to solve a problem.
We should analyze the Big O notations, or worst-case scenarios for the test cases and we will try to find the best solution.
I write regularly on Algorithm and Data Structure in
QUIZZ on Chapter Eight
Question 1: Time-Complexity has nothing to do with the execution time. Time-Complexity talks all about the better algorithm.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 2: Whenever the terms data structures and algorithms appear, time-complexity comes with them.
Option 1: The above statement is true but it is machine-specific.
Option 2: The above statement is true but it is not machine-specific.
Option 3: The above statement is true but it is not only machine-specific, but also better algorithm-specific.
Option 4: None of the above statement is true.
Answer: Option 3
=======================
Question 3: Big O notation is the most convenient way to express the worst-case scenario for an algorithm.
Option 1: It means we can compare two algorithms and decide which one is better.
Option 2: Comparing two worst case scenarios we can decide which algorithm is better.
Option 3: Comparing two best case scenarios we can decide which algorithm is better.
Option 4: None of the above statement is true.
Answer: Option 1 and 2. Both are true.
=======================
Challenge 1 : Data structures are discrete structures and hence, the algorithms are all about discrete structures. Write a program to establish a relationship between algorithms and discrete mathematics
Solution to Challenge 1 :
Language used: Java
1 //code
2
3 package fun.sanjibsinha;
4
5 public class Main {
6
7 static int i, j, totalOne, totalTwo;
8
9 public static void main(String[] args) {
10
11 for (i = 0; i <= 5; i++){
12 totalOne += i;
13 System.out.print("i = " + i);
14 System.out.println("--------");
15 for (j = 0; j <= 5; j++){
16 totalTwo += j;
17 System.out.println("j = " + j);
18 }
19 }
20 System.out.println("The total of outer loop: " + totalOne);
21 System.out.println("The total of inner loop: " + totalTwo);
22 }
23 }
24
25 //output
26
27 i = 0--------
28 j = 0
29 j = 1
30 j = 2
31 j = 3
32 j = 4
33 j = 5
34 i = 1--------
35 j = 0
36 j = 1
37 j = 2
38 j = 3
39 j = 4
40 j = 5
41 i = 2--------
42 j = 0
43 j = 1
44 j = 2
45 j = 3
46 j = 4
47 j = 5
48 i = 3--------
49 j = 0
50 j = 1
51 j = 2
52 j = 3
53 j = 4
54 j = 5
55 i = 4--------
56 j = 0
57 j = 1
58 j = 2
59 j = 3
60 j = 4
61 j = 5
62 i = 5--------
63 j = 0
64 j = 1
65 j = 2
66 j = 3
67 j = 4
68 j = 5
69 The total of outer loop: 15
70 The total of inner loop: 90
71
72 /// It is a simple algorithm of finding the total of inner loop and the outer loop. \
73 However, to do that, we need to jump sequentially; each iteration has taken place wi\
74 thin a space of discrete data structure.
Challenge 2 : How we can get the total of a series of positive integers that starts from 0 and ends at 5. Can it be done recursive way?
Solution to Challenge 2 :
Language used: Java
1 //code
2
3
4 package fun.sanjibsinha;
5
6 public class Main {
7
8 static int total;
9
10 static int getTotal(int i){
11 if (i != 0){
12 total = i + getTotal(i - 1);
13 return total;
14 } else {
15 return 0;
16 }
17 }
18
19 public static void main(String[] args) {
20
21 System.out.println("Total : " + getTotal(5));
22
23 }
24 }
25
26 //output
27
28 Total : 15
’’’’’’’’’’’’’’’’’’’’’’'’EXPLANATION’’’’’’’’’’’’’’’’’’’’’
In the above case, the same jumping of iteration occurs through a discrete structure, but in a different way. It starts from a discrete positive integer 5, and the addition process goes on until we reach the base number by calling the function recursively.
’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’
Challenge 3 : Detect the main problem in the code below and rewrite it in proper way.
Language used: Java
1 //code
2
3 package fun.sanjibsinha.timecomplexity;
4
5 import java.util.Scanner;
6
7 public class TimeOne {
8
9 static long userInput;
10
11 public static void main(String[] args) {
12 Scanner sc = new Scanner(System.in);
13 System.out.println("Enter a positive integer to test prime or not: ");
14 userInput = sc.nextInt();
15
16 for (long i = 2; i < (userInput - 1); i++){
17 if (userInput % i == 0){
18 System.out.println(userInput + " is not prime.");
19 } else {
20 System.out.println(userInput + " is prime.");
21 }
22 }
23 }
24 }
Solution to Challenge 3 : In the above code you can guess that to reach our goal we need to iterate ‘n’ number of times. Here ‘n’ is user’s input. It is called ‘order of n’ or O(n). As the value of ‘n’ starts increasing, our algorithm starts crumbling. For a value like 10 to power 6 plus 3, it takes huge to time and it simply goes out of our hands.
If we change the following line
1 for (long i = 2; i < (userInput - 1); i++){ ...
to as follows
1 for (long i = 2; i < (Math.sqrt(userInput)); i++){ ...
Our problem is solved. In the first line the program iterate more than 1 million times if user decides to give 1000003 as input. However, in the second case, the iteration reuces to in and around 1000 times for the same number.
Language used: Java