This is a beginners guide towards understanding & mastery of data structure & algorithm using Javascript.
In a quick and well-detailed series of lectures, I would be taking you on a quest of disintegrating Algorithms & Data-Structure in JavaScript, which is solemnly aimed at beginners.
Prerequisites
- Basic Knowledge of JavaScript
- Patience and Time to Read Though
And for those who might have the question “Is a functional System required?” well for this stage, I would say an emphatic No and advice you to follow through, even if you make use of a pen and a piece of paper.
The overall concept and ability to tackle challenges should be your key takeaway from this tutorial.
So let's get started.
In this part of the series, I would be taking a look at the introduction to Data-Structure & Algorithm, and of course, its importance, Big O Notation, Object & Arrays in JavaScript, and finally introduce known and unknown Problem-Solving Patterns.
Data Structure & Algorithms
Algorithms
In computer programming terms, an algorithm in its' basic term refers to a set of well-defined instructions or processes aimed at solving a particular problem or accomplishing a certain task.
It practically takes a set of inputs and produces the desired output. For example,
Quality of an Algorithm Revolves around these key points
- Its Input and output should be clearly defined.
- It should be easily understandable.
- It should be easily applied to solve similar problem sets.
There's a big misconception that algorithm has to be written in a particular programming language, whereas I am here to tell you it is not necessarily the case.
As defined above, an algorithm is a broken-down process toward solving a problem set or accomplishing a set task.
Let's take, for example, writing an algorithm to add up two numbers, leaving aside any possible edge case.
Algorithm to Add two numbers
Step 1: Start
Step 2: State variables for example let number1 = 5, number2 = 8.
Step 3: Add num1 and num2; assign the result to sum to the value of num1 & num2.
Step 4: display - return the sum
Step 5: Stop
The above might not be the most elaborate way, but I hope the message is passed.
What is the importance of an Algorithm in a real-life scenario?
To me, it simply helps complex problem-sets seem less intimidating.
Data Structure
Data structure can be referred to as storage that is used to store and organize the presentation of data. It is a way of representing data so that it can be accessed and implemented efficiently.
Choosing the right data Structure pattern is quite a big deal for a project's overall working schema.
Two Main Data Structure Categories
1. Linear Data Structures: In Linear data structures, elements are arranged in a sequence that is one after the other. But due to its structure, when implementing complex programs, It might not be the best solution.
Examples of Linear Data Structures
Array Data Structure
Stacked Data Structure
Queue Data Structure
Linked Data Structure
2. Non-Linear Data Structures: Unlike the linear data structures above, elements in non-linear data structures are not in any sequence. They are mainly arranged hierarchically.
Example of Non-Linear Data Structures
Graph Data Structure
Tree Data Structure
Map Data Structure
Importance of Knowing Data Structures
As highlighted earlier, Data Structures help you know when and how to select the best fit data structure pattern for your project or that of your company.
Let's Put a pin into data structures for now, till we circle back in later series.
BIG O
The Importance of this is quite as emphatic as it sounds 🙃.
Big O can be described as a approach, or way of generalizing or rather comparison of codes and their performance.
In much simpler terms, It's a way to know which algorithm approach or block of code is best by basic comparison standards.
Let's take a look at 2 different solutions to the problem set I saw from an online resource.
Example
Write a function that calculates the sum of all numbers from 1 up to and including the said number n.
METHOD A
function addUp (n) {
let total = 0;
for (let i = 1; i <= n; i++){
total += i;
}
return total;
}
METHOD B
function addUp(n) {
return n * (n + 1)/2;
}
Comparing METHOD A to METHOD B is where big O comes in, whereby it takes into account key criteria, which are
Speed (how fast is it)
Space (if it's of lesser memory intensity)
Readability (if it's non-ambiguous to read & understand.
Summary
For Method A, the runtime of the function is solemnly dependent on how large the value of n (i.e what it has to process).
This gives us a Time Complexity - Big O of O(N). ---> linear
While for** Method B*, the big O is **constant* since the operation the function has to perform is restricted to basic arithmetic operations which would take the same amount of time to run no matter the size of n.
giving us the Time complexity - Big O of O(1) ---> constant
Big O gives us the ability to discuss the impact the input of a function has on its runtime.
whereas a function of n => f(n)
f(n) = n linear
f(n) = n^2 quadratic
f(n) = 1 constant
Simplifying Big O
Let's look at various case studies and their simplified term
1. O(2n) = O(n)
2. O(500) = O(1)
3. O(13n^2) = 0(n^2)
4. O(n + 1) = O(n)
5. O(10000n + 5) = O(n)
6. O(n^2 + 5n + 8) = O(n^2 + n) === O(n^2)
kindly note
Constant and Smaller terms don’t really matter
Arithmetic Operation is Constant
Variable assignments are constant
Accessing elements in an array is constant
For a loop, the complexity of the said loop depends on the length of the loop multiplied by the complexity of what happens in the loop.
Time & Space Complexity rule of thumb
Most primitive are constant (booleans, numbers, undefined & null)
Strings are linear ( O(n) depends on the length of the string)
Let's check out an example to further explain space complexity.
for instance, a function that triple each element in an array,
function triple(arr){
let newArray = [];
for (let i = 0; i < arr.length; i++){
newArray.push(3 * arr[i]);
}
}
In summary, the length of the input array (arr) would directly impact the length of the new array.
therefore giving us a space complexity of O(n)
Analyzing Performance of Array & Object
The Big O of JavaScript Object
Objects are unordered data structures that are stored in a key-value pair
Perks
It is useful in cases you don't need an order
Fast access & Insertion
Insertion O(1)
Removal O(1)
Searching O(N)
Access O(1)
Object Methods
Object.keys O(N)Object.values O(N)Object.entries O(N).hasOwnProperties O(1)
The Big O of JavaScript Array
Arrays are ordered data structures.
Perk
- Useful in cases where the order is needed.
Access. O(1)
Searching O(N)
Insertion & Removal both depends on the position or rather index in which the operation is to be performed. but for the last element, there are both O(1)
Thats why .push and .pop are primarily faster than .shift and .unshift
Some Basic Array Methods
-
.push O(1) -
.pop O(1) -
.shift O(N) -
.unshift O(N)
I would strongly advise you to visit the link above from time to time and get an in-depth knowledge of Javascript array.
Next Topic
Popular Problem Solving Pattern
In the coming lecture, we would have hands-on practice towards common problem-solving patterns in algorithms and at least have an idea of where to start form while tackling problem sets.
My goal is not to bore you or rather impress with ambiguous words but rather convey in simple terms what the said subject matter is all about. On that note, would see you in the upcoming part.
Top comments (0)