Big O Notation

Big O Notation is a relative representation of an algorithm’s complexity. It describes how an algorithm performs and scales by denoting an upper bound of its growth rate.

What to remember : the less time an algorithm takes to complete, the better.

Now let’s look at the syntax of O(n2)

n is the number of elements that the function receiving as inputs. So, this example is saying that for n inputs, its complexity is equal to n2.

O(1) : Constant Time Algorithms

It doesn’t matter what n inputs is, above. This piece of code takes a constant amount of time to run. It’s not dependent on the size of n.

int n = 100;
System.out.println("ShootSkill input is: "+n);

O(log n) : Logarithmic Time Algorithms

O(log n) represents a function whose complexity increases logarithmically as the input size increases, an example is is the binary search algorithm.

public boolean containInput(List<Integer> numbers, int comparisonNumber) {
int low = 0;
int high = numbers.size() - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (comparisonNumber < numbers.get(middle)) {
high = middle - 1;
} else if (comparisonNumber > numbers.get(middle)) {
low = middle + 1;
} else {
return true;
}
}
return false;
}

O(n) : Linear Time Algorithms

O(n) represents the complexity of a function that increases linearly and in direct proportion to the number of inputs, a simple for loop will do the job :

for (int i = 0; i < n; i++) {
System.out.println("ShootSkill input is: "+i);
}

O(n2) : Polynomial Time Algorithms

O(n2) represents a function whose complexity is directly proportional to the square of the input size.

Adding more nested iterations through the input will increase the complexity which could then represent O(n3) with 3 total iterations and O(np) with p total iterations.

for (int i = 1; i <= n; i++) {
  for(int j = 1; j <= n; j++) {
    System.out.println("ShootSkill input is: " + i + " and " + j);
  }
}

checkout my website https://shootskill.com/