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");
	}