# Big O

## Introduction

Big O is the metric used to describe the efficiency of algorithms and refers to the worst case for the algorithm.

• Common Runtimes
• O(logN), O(NlogN), O(N), O(N*2), O(2^N)

Time Complexity: An amount of time required to complete an algorithm.
Space Complexity: An amount of space required by an algorithm.

Factors for Time Complexity

• Ignore the Constants: Big O allows us to ignore the constants as it describes the rate of increase as the value of n scales, i.e.: O(2n) and O(n) have the same efficiency.
• Ignore the Non Dominant terms: i.e O(N + logN) becomes O(N)

## Scenarios

### 1) N Runtimes

Example -: Find the sum of number – O(n)

```	private static int sumOfInput(int i) {
if (i <= 0) {
return 0;
}
return i + sumOfInput(i - 1);
}
```

Example -: Reverse an array – O(n)

```	private static void reverse(int[] array) {
for (int i = 0; i < array.length/ 2; i++) {
int other = array.length - i - 1;
int larger = array[i];
array[i] = array[other];
array[other] = larger;
}
}
```

Example -: Print Factorial – O(n)

```	private static int factorial(int i) {
while (i == 0) {
return 1;
}
return i * factorial(i - 1);
}
```

Example : – Print Fibonacci numbers

```	private static int fibonacci(int i, int[] array) {
if (i == 0) {
return 0;
} else if (i == 1) {
return 1;
} else if (array[i] != 0) {
return array[i];
} else {
array[i] = fibonacci(i - 1, array) + fibonacci(i - 2, array);
return array[i];
}
}
```

### 2) Log N Runtimes

Usually in scenarios when the workspace reduces in half in every iteration: Ex – Binary Search
Another way to calculate is to think how the BigO changes with n, that is work time increases only when n doubles. 2^x = n => x = logn

Example : – Print Power of two till the Given number

```	private static int powerOfTwo(int i) {
if (i <= 1) {
return 1;
}
int prev = powerOfTwo(i /2 );
int current = prev * 2;
System.out.println(current);
return current;
}
```

### 3) 2^N Runtimes

This runtime comes into effect when there are twice as many calls on the one level above it as in the below example.

Example -: Print Fibonacci – O(2*n)

```	static int fib(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
```

Example -: Print all permutations of a String – O(n*2 + n!)

``````	private static void permutation(String name, String prefix) {
if (name.length() == 0) {
System.out.println(prefix);

} else {
for (int i = 0; i < name.length(); i++) {
String rem = name.substring(0, i) + name.substring(i + 1);
permutation(rem, prefix + name.charAt(i));
}
}
}``````

#### 4) O(sqrt(N) Runtimes

Example -: Check If Prime- O(sqrt(n))

```	private static boolean isPrime(int i) {
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
return false;
}
}
return true;
}
```

Example -: Find Square root- O(sqrt(n))

```	public static void main(String[] args) {
int n = 10;
for (int i = 0; i * i <= n; i++) {
if (i * i == n) {
System.out.println(" SquareRoot : " + i);
}
}
System.out.println(" No SquareRoot");
}
```

error: Content is protected !!
Scroll to Top