**Big-O notation**

In this tutorial, we are going to discuss about the Big-O notation. Big-O notation is a mathematical notation that is used to describe the performance or complexity of an algorithm, specifically how long an algorithm takes to run as the input size grows.

Understanding Big-O notation is essential for software engineers, as it allows them to analyze and compare the efficiency of different algorithms and make informed decisions about which one to use in a given situation. In this tutorial, we will cover the basics of Big-O notation and how to use it to analyze the performance of algorithms.

###### What is Big-O?

Big-O notation is a way of expressing the time (or space) complexity of an algorithm. It provides a rough estimate of how long an algorithm takes to run (or how much memory it uses), based on the size of the input. For example, an algorithm with a time complexity

of means that the running time increases linearly with the size of the input.*O*(n)

###### What is time complexity?

Time complexity is a measure of how long an algorithm takes to run, based on the size of the input. It is expressed using Big-O notation, which provides a rough estimate of the running time. An algorithm with a lower time complexity will generally be faster than an algorithm with a higher time complexity.

###### What is space complexity?

Space complexity is a measure of how much memory an algorithm requires, based on the size of the input. Like time complexity, it is expressed using Big-O notation. An algorithm with a lower space complexity will generally require less memory than an algorithm with a higher space complexity.

###### Examples of time complexity

Here are some examples of how different time complexities are expressed using Big-O notation:

: Constant time. The running time is independent of the size of the input.*O*(1)

: Linear time. The running time increases linearly with the size of the input.

(n)*O*

: Quadratic time. The running time is proportional to the square of the size of the input.

(nÂ²)*O*

: Logarithmic time. The running time increases logarithmically with the size of the input.

(logn)*O*

: Exponential time. The running time increases exponentially in the size of the input.

(2*O*^{n})

Big-O notation uses mathematical notation to describe the upper bound of an algorithmâ€™s running time. It provides a way to compare the running time of different algorithms, regardless of the specific hardware or implementation being used.

Itâ€™s important to note that Big-O notation only provides an upper bound on the running time of an algorithm. This means that an algorithm with a time complexity of

) could potentially run faster than an algorithm with a time complexity of *O*(n

in some cases, depending on the specific implementation and hardware being used.*O*(logn)

Additionally, Big-O notation only considers the dominant term in the running time equation. For example, an algorithm with a running time of

would be simplified to .*O*(nÂ²+n)

**Example algorithms and their time complexities**

#### 1. Linear searchâ€Š-â€Š*O*

(n)

*O*

(n)Here are a few examples of algorithms along with their time complexities expressed using Big-O notation:

```
package com.ashok.datastructures.linearsearch;
/**
*
* @author ashok.mariyala
*
*/
public class LinearSearch {
public static int linearSearch(int[] arr, int x) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {3, 5, 7, 9, 11};
int x = 7;
System.out.println(linearSearch(arr, x));
}
}
```

This linear search algorithm has a time complexity of â€Š

, since the running time is directly proportional to the size of the input. If the input size is

(n)*O*`n`

, the linear search will take n steps to complete.

**2. Binary searchâ€Š-â€Š ***O*

(logn)

*O*

(logn)

```
package com.ashok.datastructures.binarysearch;
/**
*
* @author ashok.mariyala
*
*/
public class BinarySearch {
public static int binarySearch(int[] arr, int x) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < x) {
low = mid + 1;
} else if (arr[mid] > x) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
System.out.println(binarySearch(arr, x));
}
}
```

This binary search algorithm has a time complexity of

, since the running time increases logarithmically with the size of the input. If the input size is

(logn)*O*`n`

, it will take approximately `log(n)`

steps to complete the binary search.

**3. Bubble sort – ***O*

(nÂ²)

*O*

(nÂ²)

```
package com.ashok.datastructures.bubblesort;
/**
*
* @author ashok.mariyala
*
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
```

This bubble sort algorithm has a time complexity of

, since the running time is quadratic in the size of the input. If the input size is n, it will take approximately nÂ² steps to complete the bubble sort.

(nÂ²)*O*

Thatâ€™s all about the Big-O notation. If you have any queries or feedback, please write us email at **contact@waytoeasylearn.com**. Enjoy learning, Enjoy Data Structures.!!