How to calculate time complexity of any program in Java
Java :
Java's syntax and principles are derived from the C and C++ languages. We know that java is one of the programming language. The main feature of java which is not in C or object oriented programming language is platform independence.
Not only the platform independence there are many other features in java such as secure, highly interpreted, robust, portable etc. We have a JVM ( Java Virtual Machine ) , JRE ( Java Runtime Environment ) , JDK ( Java Development Kit ). It is used to convert .class file to .exe file.
Time complexity :
The length of the input determines how long it takes an algorithm to run, which is known as temporal complexity. It calculates how long it takes for each algorithm's code statement to run. It won't look at an algorithm's overall execution time.
Instead, it will provide details regarding the variation it may be increase or decrease in execution time when an algorithm's number of operations whether it may be increase or decrease. Yes, as the definition states, the only factor affecting the amount of time required is the length of the input.
The efficiency of an algorithm can be determined by its time complexity. Even if we are aware that there are other ways to approach an issue in programming, understanding how an algorithm operates effectively might improve our job.
Understanding how to analyze programs and algorithms utilizing Time complexity might help us become more productive programmers by getting them to perform in the desired ideal conditions.
The definition of the algorithm is as shown below :
1. Given two input matrices, one of which is an n-by-n square matrix
2. Using the function, the values of each member in both matrices are chosen at random.
3. Initialized with an output matrix that contains 0 values and has an order matching the order of the input matrix.
4. The product of multiplying each element of X by each element of Y is recorded in the result matrix.
5. After that, the matrix is changed to a list type.
6. The total value for each item in the result list is summed to provide the answer.
Let's say that the cost function C is measured in terms of the amount of time it takes a function to run, and that n is the number of times the statement will be executed by an algorithm.
For instance, if the algorithm is set up to execute the print function 1000 times and it takes 1 microsecond (C) to do so (n),
Thus the total run time is equal to (C * n) = 1 microsecond multiplied by 1000, or 1 millisecond.
There are different kind of notations to mention the time complexity such as
- O ( 1 ) = > constant
- O ( n ) = > Linear
- O ( n power 2 ) = > Quadratic
- O ( log n ) = > Logarithmic
- O ( n power p ) = > Polynomial
- O ( k power n ) = > Exponential
Now let us see some examples and let us calculate the time complexity of that programs:
Example 1:
int n = 5;
System.out.println ( n );
System.out.println ( n );
Here the time complexity of the above code is O ( 1 ) because how many times we print then value the time complexity remains constant.
Example 2:
for ( int i=0 ; i<n ; i++)
{
System.out.println ( i );
}
Here the time complexity of the above code is O ( n ) since the loop repeats ‘ n ‘ times.
Example 3:
for ( int i=0 ; i<n ; i=i*2)
{
System.out.println ( i );
}
Here the time complexity of the above code is O ( log n ) .
Example 4 :
for ( int i=0 ; i<n ; i++)
{
for ( int j=0 ; j<n ; j=j*2 )
{
System.out.println ( i );
System.out.println ( j );
} // j loop
} // I loop
Here the time complexity of the above code is O ( n log n ) since the outer loop repeats ‘ n ‘ times and the inner loop has logarithmic function.
As shown above we can calculate the time complexity of any of the program. We can also use the step count method to calculate the time complexity.