Time complexity

An algorithm can be written in many ways but some codes perform better than others because those codes can run in less time as compare than others for the same inputs. Those codes have less time complexity.

Time complexity can be defined as the time taken by algorithm increases with an increase in the input size.

Time complexity can be measured in the following way:-

1. big-oh — Upper bound
2. big-omega — Lower bound
3. Theta — Avg. Bound

a)Big oh(O)

big oh is used to measure worst-case scenarios

we will take an example of searching for this s we have do=ifferent search methods available among then most common are linear search and binary search. Below we have a list of few elements and we want to search for a particular element lets take it as 7.

array=95,6,47,90,32,67,7,10,2,65,89

Linear search will start scanning from the left-hand side and iterate over all elements one by one until it finds the required element. So, in the above example, we will get our element after 7 comparisons. Now lets search for 30, but in this case, it will iterate through all elements but the search will be unsuccessful.

Worst case scenario for linear search-

If we search for an element present in the last index of the array, the total number of iteration that will take is the length of that array ie: element 89 and it can also be written as O(n) where n is the length of an array.

How can we find big Oh

1. Find the fastest growing term in the equation.
2. Take out the constant and coefficient from the fastest-growing term

best time complexity -

1<log n<root(n)<n<nlogn<n²<n³<n^n

b) Big Omega

Is a way to express the lower bound of that algorithm. It measures the best-case runtime complexity.

-Best case scenario for linear search-

If our required element is present in the first index then we need only one iteration and it will take constant time, like if our searched element is 95. Can also be written as O(1).

More Examples for different time complexity-

1)Constant time O(1):

=>int x=1000;

System.out.println(x);

2)n log(n):

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

3) liner time algorithem

for (int i = 0; i < n; i++) {
System.out.println(“print I “ + i);
}

4) log n algorithem

int n=100;

int c=10;

for(int i=n;i>0;i=i/c){

System.out.println(i);
}