Repository files navigation

This is an attempt to implement all kind of widely usedAlgorithms andData Structures in the programming world using JavaScript. Thus the termAlgoDS 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 findREADME 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

• Arithmetic operations are always constant
• Assignment of a variable is also constant
• Accessing elements in an object by its key is constant
• Accessing elements in an array by its index number is constant
• The complexity of a loop is the amount of iteration it takes to complete the loop. How many time the loop runs again and again is the total complexity.

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

• Constant Time =>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.
• Logarithm Time =>log(n)Doubling the inputs will not double the amount of work required
• Linear Time =>nIterating over all the elements in a collection once. Usually if any program has onefor loop, it can have linear time complexity
• Quasilinear Time =>n * log(n)Doubling the elements will double the amount of work required
• Quadratic Time =>n^2Every element in a collection has to be compared to every other element
• Exponential Time =>2^nAdding a single element will double the work required.

       O(n^2)|       / / O(nlogn)/ O(n)|      / /        /|     / /       /|    / /      /|   / /     /|  / /    /| / /   /|/ /  /----------------------- log(n)| / /_________________________ O(1)|//___________________________

• Iterating through a collection using a single for loop =>O(n)
• Iterating through half of a collection using a single for loop =>O(n)
• Iterating through two different collection using separate for loop =>O(n + m)
• Two nested loop iterating over same collection =>O(n^2)
• Two nested loop iterating over different collection =>O(n * m)
• Most of the Sorting Algorithm =>O(n * log(n))
• Searching on a Sorted Collection =>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 times123456 => 654321 n times

• Boolean, Numbers, undefined, null including most of the primitives are constant
• String takes the amount of character, means the length is its required space. Thus it is O(n)
• Objects takes the number of keys it has. Thus it is O(n)
• Arrays are also same. It takes the total number of elements it has(its own length). This it is also O(n)

Logarithmic values often can be very confusing. But there also very easy to understand. Like if we explain what doeslog2(8) = 3 means:

log2(8)=3=>2^3=8log(2)(value)=exponent=>2^exponent=value

And alsolog2 andlog 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

constanObj={name:'Zonayed Ahmed',age:22,gender:'Male'}

• Insertion will take O(1)
• Removal will also take O(1)
• Accessing anything will also take 0(1)
• Searching anything will take 0(n)

We can analyze the performance of JavaScript's built-in array

constanArr=[0,1,2,3,4,5,6,7,8,9, ...,1000]

• Accessing an element by its index number will take O(1)
• push() andpop() methods also take O(1)
• Butshift() andunshift() 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 front
• Searching will take O(n)

• Understand the main problem very clearly at First
• Try to find out some example, what type and amount of data it will take and also what it will return. Try to understand them.
• Now breaks them down. How this type of input can give that type of output. Break them out one by one
• Now solve those problem one by one, simply
• Now take a look at the solution and try to refactor it maintaining DRY Principal

Some problem solving patterns are widely used to simplify the solution like:

• Frequency Counter
• Multiple Pointers
• Sliding Window
• Divide and Conquer
• Dynamic Programming
• Greedy Algorithms
• Backtracking...and more to come

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 optimalruntime complexity for adding, removing and some basic operations in the record. Some example of mostly used Data Structure

• Array
• Object
• Stack
• Queue
• Linked List
• Tree
• Graph
• Set
• Hash Table