🛠🛠🛠Widely used Algorithms and Data Structures using JavaScript 🛠🛠ðŸ›
This is an attempt to implement all kind of widely used Algorithms and Data Structures in the programming world using JavaScript. Thus the term AlgoDS is used as a name of this repository. Anyone can use it as a reference to implement those problems. If you have any suggestion, then please make an issue or contact me, I will be grateful to you.
Most of the implementations are done using pure functions so that anyone can use them as well if they want. index.js
files are made for testing purpose. Besides, you will find README file in every problem that will illustrate the problem so that you can understand them easily.
It allows us to calculate how the runtime of an Algorithm grows as the inputs grow
Describe the performance of an algorithm. How much processing power or time is required to run an algorithm if we double the amount of input
O(1)
The algorithms will always take the same amount of time no matter how large our input data is or small. It is always the same. Thus it is called as constant time.log(n)
Doubling the inputs will not double the amount of work requiredn
Iterating over all the elements in a collection once. Usually if any program has one for
loop, it can have linear time complexityn * log(n)
Doubling the elements will double the amount of work requiredn^2
Every element in a collection has to be compared to every other element2^n
Adding a single element will double the work required. O(n^2)
| / / O(nlogn)/ O(n)
| / / /
| / / /
| / / /
| / / /
| / / /
| / / /
|/ / /----------------------- log(n)
| / /_________________________ O(1)
|//___________________________
O(n)
O(n)
O(n + m)
O(n^2)
O(n * m)
O(n * log(n))
O(logn)
The amount of space in the memory required by that particular Algorithm. How much more memory is required by doubling the problem set.
123 => 321 => n times
123456 => 654321 n times
Logarithmic values often can be very confusing. But there also very easy to understand. Like if we explain what does log2(8) = 3
means:
log2(8) = 3
=> 2^3 = 8
log(2)(value) = exponent => 2^exponent = value
And also log2
and log
is same. We can omit 2 in this case
We can analyze the JavaScript's built-in objects to find out its various complexity to accomplish various task
const anObj = {
name: 'Zonayed Ahmed',
age: 22,
gender: 'Male'
}
We can analyze the performance of JavaScript's built-in array
const anArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 1000]
push()
and pop()
methods also take O(1)shift()
and unshift()
will take O(n) as all the element's index number has to be changed in order to remove or add any element from the frontSome problem solving patterns are widely used to simplify the solution like:
This pattern uses objects or sets to collect values/frequency of values. Thus most of time nested loops or O(n^2) time complexity can be avoided
Creating pointers or values that correspond to an ndex or position and move towards beginning, end or middle based on a certain condition
Ways of organizing information with optimal runtime complexity for adding, removing and some basic operations in the record. Some example of mostly used Data Structure