## What is Big O notation?

**Big O notation** is used to measure how the running time or space requirements for our program grows as input grows.

- Measuring running time growth is time complexity. (In this post we focus on time complexity)
- Measuring space growth is space complexity.

## Rules to determine time complexity

- Keep fastest growing term.
- Drop constants.

Big O refers to very large value of 'n' (n = size) where time, **t = an^2 + bn + c**.

For example, if we have a function like,

t = 5n^2 + 3n + 20

When value of 'n' is very large, bn+c becomes irrelevant.

ie; an^2 is very larger than bn+c.

For example; if n = 1000 then,

t = 5 * 1000^2 + 3*1000+20 = 5000000 + 3020; where 3020, a small value becomes irrelevant.

## Different time complexities

Here we discuss about a few of them.

#### 1. O(n)

def foo(arr): size(arr) -> 100 -> 0.22ms

def foo(arr): size(arr) -> 1000 -> 2.30ms

Here time increases as array size increases; time proportional to size(arr).

n = size(arr), b= constant

t = a*n + b

- Keep fastest growing term => t = a * n (b is constant)
- Drop constants => t = n ( a is constant)

Therefore;**t = O(n)**

*Example program for t = O(n): To get square numbers*

```
def get_squared_numbers(numbers):
squared_numbers = []
for n in numbers:
square_numbers.append(n * n)
return squared_numbers
numbers = [2, 5, 8, 9]
get_squared_numbers(numbers)
#returns [4, 25, 64, 81]
```

#### 2. O(1)

def foo(arr): size(arr) -> 100 -> 0.22ms

def foo(arr): size(arr) -> 1000 -> 0.23ms

time, t = a * n + b -> t = a * n ( b constant) -> t = n (dropping constants(a))

n = 1 => t = 1

Therefore, **t = O(1)**

*Example program for t = O(1)*

```
def find_first_pe(prices, eps, index):
pe = prices[index]/eps[index]
return pe
```

#### 3. O(n^2)

*Example Program for O(n^2): To find duplicates from the list*

```
numbers = [3, 6, 2, 4, 3, 6, 8, 9]
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] == numbers[j]:
print(numbers[i] + " is a duplicate.")
break
```

*Also there is O(log n), O(2^n) time complexities.*

**Happy learning**

#competitiveprogramming #dsa #datastructures #algorithms