**by BehindJava**

# What is Big-O notation

In this blog, we are going to learn about Big-O notation with examples.

# Big-O Notation

- This notation has been developed as the standard for comparing algorithm.
- The main aim of this notation is to identify the dominant term in the determining the time complexity of an algorithm.
**Definition**: Let f(n) and g(n) be the two functions where n is +ve integer, then we can say that f(n) is of the order g(n),generally written as: f(n)=O(g(n)).

if and only if there exists a constant c>0 such that.

|f(n)|<= c|g(n)|for n>=n0, where n0 is an arbitrary large +ve number.

**Example 1**: This code segment will work in linear time which means for each input you are giving, some “1” amount of operation inside the loop is performed.

```
for(int i = 0 ; i < n ; i ++)
{
// Do something
}
```

- N(no of input) * 1 (No of operation performed for each input) = N
- This is known as O(N).

**Example 2**:This code segment will work in Quadratic time which means for each input you are giving, “N” amount of operation inside the loop is performed.

```
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
// Do something
}
}
```

- N(no of input) * N (No of operation performed for each input) = N^2
- This is known as O(N^2).

Therefore we can say that big O (n^2) is having higher or bad complexity due to nested loop.

# Other Asymptotic Notations

**Big Omega Notation**: Big-O notation is used for analyzing the upper bound of the function, the omega notation is used when the function defines a lower bound for the function f(n). It is formally defined as- If and only if there exists a +ve constant c and n0 such that f(n)>=c.g(n) for n>n0. The definition is read as function f(n) is omega of g(n) if there exists a +ve number c such that f(n) is at least equal to c.g(n) for almost all values of n where n>n0.
**Big –Theta Notation**: Theta notation can be described as f(n)=theta g(n)if and only if there exits +ve constant c and n0 such that f(n)=c.g(n) for all n>=n0 . In other words, for large n, g(n) is tight bound for f(n) i.e. g(n) is both lower and upper bound for f(n).

# Special Classes of Algorithms

- Logarithmic: O(log n)
- Linear: O(n)
- Quadratic: O(n^2)
- Polynomial: O(n^k), k >= 1
- Exponential: O(a^n), a > 1