JavaScript Algorithms — 01

An algorithm is a set of well-defined instructions to solve a particular problem.

Let’s say you love coffee, ☕️ by the way, all devs 👨🏻‍💻 love coffee! To make a coffee, you need ingredients, you have to follow a few instructions, and we call it a recipe. There may be so many recipes out there, but you have to choose what’s good for you. So after following the recipe you can make a good coffee.

When it comes to programming we do also have many algorithms to solve different kind of problems, So you have to choose what is the best algorithm for that particular task.

Algorithm to add two numbers

recipe of adding two numbers 😆

Characteristics of Algorithms

1. Well defined inputs and outputs
2. Each step should be clear
3. Language independent

Why do we need Algorithms?

When we are solving problems we have to do it efficiently so Algorithms are really helpful for that. Also we can solve one problem in many ways using different algorithms.

Are algorithms really efficient?

This depends on few factors.

1. Performance of the computer that the program runs on
2. The programming language which is used to develop the program
3. The OS of the computer
4. … etc

We can evaluate the performance of the algorithm by its input size. we have two type of evaluation methods

1. Time Complexity — Amount of time taken by an algorithm to run as a function of input size.

If you have less memory to work with, you should pick a solution that is relatively slower but needs less space.

2. Space Complexity — Amount of memory taken by an algorithm to run as a function of input size.

If your application has plenty of memory to work with, you don’t need to worry about space complexity. :)

How do we represent complexity?

1. Big-O Notation — Worst case complexity
2. Omega Notation — Best case complexity
3. Theta Notation — Average case complexity

Big-O Notation

The worst case complexity of an algorithm is represented using the Big-O Notation.

count the number of times a statement executes based on the input size.

if we take the above example code, and lets assume n = 10.

• the LINE NO 2 runs one time
• the LINE NO 5 runs ten times ( since n = 10 )
• the LINE NO 8 runs one time
• So the runtime is 10 + 2, if we generalise, its n + 2. our time complexity is depend on the input size. in this case its n.

ii. Big O focuses on the bigger picture without focusing on the minor details

n + 2

• n = 100 -> 100 + 2
• n = 1000 -> 1000 + 2
• n = 10000 -> 10000 + 2
• …
• …
• n = 1000000 -> 1000000 + 2

so in here +2 is very insignificant. so we can drop it and consider just n, since n contributes most to the value than the other minor details.

O(n) — Liner Time complexity

An algorithm has linear complexity if the time it takes to solve the problem increases linearly with the size of the input. This means that if the input size doubles, the time it takes for the algorithm to solve the problem will also double.

O(1) — Constant Time complexity

An algorithm has constant time complexity if the time it takes to solve the problem is independent of the input size. This means that no matter how large the input size is, the time it takes for the algorithm to solve the problem remains constant.

Constant time complexity is generally considered to be the most efficient level of complexity for an algorithm, as it means that the algorithm will always take the same amount of time to solve a problem, regardless of how large the problem is. However, achieving constant time complexity is not always possible or practical, and in many cases, an algorithm with a higher complexity may be necessary to solve the problem at hand.

Space Complexity

Space complexity refers to the amount of memory or storage space required by an algorithm or a program to solve a problem. It is a measure of the maximum amount of memory that the program requires to store data, temporary variables, and other information during its execution.

O(n) — Liner Space complexity

if the space required by a program increases linearly with the input size, we say that the space complexity of the algorithm is O(n), where n is the input size.

O(1) — Constant Space complexity

If the space required by the program is constant regardless of the input size, we say that the space complexity is O(1).

Big-O Complexity Chart

image is taken from freecodecamp.org

Well, enough theory will see some practical usages in next articles.

Thanks ;)
TS!