A Primer to Algorithms

Generally, a problem can be solved in many different ways and each way has its own tradeoffs(pros and cons). Algorithms are sets of well defined instructions to solve a particular problem or to achieve a desired result.

Algorithms must include:

• Well defined set of inputs and outputs - Algorithms require clearly defined inputs and outputs to ensure consistent applicability across various datasets, clarifying what the algorithm needs as input and what it will yield as output.

• Clear & unambiguous steps - Each step in an algorithm must be precisely defined and unambiguous. This ensures that anyone implementing the algorithm can follow the steps without confusion. Ambiguity in the steps can lead to incorrect results or unexpected behavior.

• Language independence - Ideally, algorithms should be language-independent, meaning they can be implemented in any programming language without significant modifications. This allows developers to choose the most suitable language for their project while still benefiting from the algorithm's logic and efficiency.

Performance

Generally, performance is talked about as an absolute measure. The absolute running time of an algorithm cannot be predicted since it depends on a number of factors like programming language, hardware, quality of operating system etc.

Algorithms in computer science are best evaluated based on the size of the input —

• Time complexity - This measures the amount of time an algorithm takes to execute as a function of the length of its input

• Space complexity - This measures the amount of memory an algorithm uses as a function of the length of its input. It helps in understanding the algorithm's memory requirements and efficiency.

How to represent complexity

Asymptotic notations

• Big O notation(O) (worse case complexity) - Indicates the maximum amount of time or space required by the algorithm for any input size. Often used to analyze the worst-case scenario and determine the algorithm's scalability.

• Omega notation(Ω) (best case complexity) - Indicates the minimum amount of time or space required by the algorithm for any input size.

• Theta notation(Θ) (average case complexity) - Represents both upper and lower bounds or average-case complexity of an algorithm.

Worst case complexity (Big O notation) is best used to determine the performance of an algorithm

Big O Notation

function (n){

The characteristics of big O notation is that it

• is expressed in terms of input

• focuses on the bigger picture

For example, in this JavaScript code above,

the statement:

• let sum runs once

• for loop runs based on the number of n

• return sum runs once.

So, the total number of time based on big-O is (n+2) ---- expressed in terms of input which is n

As n becomes larger (thousands, hundreds of thousands...), the 2 becomes insignificant. It is simply O(n) ---- focuses on the bigger picture. The constants and lower-order terms are disregarded in Big O notation because they become insignificant as the input size grows larger.

O(n) is called a linear complexity because the number of times it runs correlates directly with the input n

Other big O complexities are

• O(1) — Constant and independent of the input. It runs just once.

• O(n²) — Quadratic. Observed in algorithns with two nested loops. The relationship between the input and the number of times it runs is not linear

• O(n³) — Cubic. Observed in algorithns with three nested loops.

• O(log n) — Logarithmic. Showcases algorithms that exhibit efficient runtime growth as the input size increases.