Introduction to Algorithms

What is an Algorithms?

An algorithm is a set of step by step or well-defined instructions for solving a specific problem.

This means that the method you use to arrive at the same solution may differ from mine, but we should both get the same result.

Because there are various ways to solve a problem, there must be a way to evaluate these solutions or algorithms in terms of performance and efficiency (the time it will take for your algorithm to run/execution and the total amount of memory it will consume).

What is Big O?

Big O or Big O notation, represents an algorithm’s worst case complexity.

It uses algebraic terms to describe the complexity of an algorithm.

Big O defines the runtime required to execute an algorithm identifying how the performance of your algorithm will change as the input size grows.

But it does not tell you how fast your algorithm’s runtime is.

Big O notation measures the efficiency and performance of yo algorithm using time and space complexity.

What is Time and Space Complexity?

An algorithm’s time complexity specifies how long it will take execute an algorithm as a function of its input size.

Similarly, an algorithm’s space complexity specifies the total amount of space memory required to execute an algorithm as a function of the size of the input.

In Big O, there are six major types of complexities (time and space):

1. Constant: O(1)
2. Linear time: O(n)
3. Logarithmic time: O(n log n)
4. Quadratic time: O(n^2)
5. Exponential time: O(2^n)
6. Factorial time: O(n!)

• O(1): Constant complexity.
• O(logn): Logarithmic complexity.
• O(n): Linear complexity.
• O(nlogn): Loglinear complexity.
• O(n^x): Polynomial complexity.
• O(X^n): Exponential time.

Amon them

O(1) – Excellent/Best
O(log n) – Good
O(n) – Fair
O(n log n) – Bad
O(n^2), O(2^n) and O(n!) – Horrible/Worst

• When your calculation is not dependent on the input size, it is a constant time complexity (O(1)).
• When the input size is reduced by half, maybe when iterating, handling recursion, or whatsoever, it is a logarithmic time complexity (O(log n)).
• When you have a single loop within your algorithm, it is linear time complexity (O(n)).
• When you have nested loops within your algorithm, meaning a loop in a loop, it is quadratic time complexity (O(n^2)).
• When the growth rate doubles with each addition to the input, it is exponential time complexity (O2^n).

https://bigocheatsheet.io

Thanks for your time!