DSA's intro to your development journey

In this blog I intend to communicate the most basic unit of information that we need to understand to start DSA.

Most frontend developers like myself often question the need to do DSA when not much of DSA is required in our development usually. But sometimes it does makes a difference. Every point for performance improvement is critical if you don't want users to close the tab because your website is too slow. Understanding of time complexity and efficient algorithms helps you write better (more optimized) code which helps with scalability.

In this blog we will understand: -

• What are data structures?
• What is time complexity?
• What is space complexity? and
• How do we simplify complexity analysis?

Let's start...

What are data structures?

Data structures can be defined by 3 parameters: -

• it is a collection of data,
• the data items has a relationship or a linking factor, and
• we can perform functions or operations on the data.

For an example we can analyze an array arr = [12, 54, 86, 3, 94] based on our parameters.

1. collection of data (✔️)
2. a relationship or a linking factor {each array element has a unique index} (✔️)
3. can perform functions or operations on the data {ex: arr.push(7)}(✔️)

Therefore, an array is a valid data structure.

What is a time complexity?

Time complexity is the relationship between input and operations performed in an algorithm.

input ↑ operations ↑

Time complexity is not calculated in seconds because of two factors: -

• on different computers, the time taken for an algorithm can differ because of the difference in the hardware,
• on the same computer, it is also not certain that the time taken by an algorithm (with same input) is same all the time. (not convinced for this point myself - if someone could point out the logic in the comments that would be great).

Therefore, because of the above-mentioned points, the time complexity is not calculated by time taken in seconds but rather by a factor that remains across all the hardware. That common factor is number of operations.

Regardless of the hardware, the number of operations would be same for an algorithm if the provided input is the same.

Let's understand time complexity with an example too.

Example: We need to get the sum of N numbers. Now, we can solve this task with 2 approaches.

Approach 1: we solve this with the formula (N * (N-1))/2 

Approach 2: we get the sum by, sum = (N-1) + (N-2) + ... + 1

For approach 1: -
This approach has 3 operations.

• If N = 3: number of operations = 3
• If N = 300: number of operations = 3

This means, if value of N increases, the number of operations remains the same. Time complexity of this approach is constant.

For approach 2: -
This approach has (N-1) + (N-2) operations.

• (N-1) = operations to get (N-1) numbers before N, and
• (N-2) because addition operation happens (N-2) times after getting all the numbers

So, this approach requires 2N - 3 operations total.

• The number of operations will increase as the value of N increases

To represent time complexity, we use Big O notation. For approach 1, since the time complexity remains constant regardless of the input value, the time complexity is O(1) which is called as order of 1. And for approach 2, the number of operation increases linearly as the input value increases, so the time complexity is O(2N-3).

Some common time complexities: -

• O(1): constant,
• O(N): linear - algorithm has to traverse array of inputs or write a loop once,
• O(logN): binary search algorithm,
• O(NlogN): merge sort algorithm,
• O(N^2), O(N^3), etc: case of nested loops. 2 loops, complexity O(N^2) and so on...
• O(2^N): fibonacci,
• O(N!)

Simplify complexity analysis (Big O): -

• Drop the constants. Ex: N^2 + 3
• Drop insignificant terms. Ex: N^3 + N

The reason for above mentioned suggestion is that when N has a big value say N=10000, 3 operations or N operations would not add much significance to N^2 or N^3 operations.

• Do not drop another input M. Ex: O(N^3 + M + 2) can be simplified as O(N^3 + M) > The reason for above mentioned suggestion is because inputs can be provided such that M has a significant value say 10,000 whereas N = 1.

Based on above explanation, the time complexity for approach 2 can be simplified to O(N).

What is space complexity?

Space complexity is the relationship between input and auxiliary space required by an algorithm.

• For space complexity, we do not consider the space that is required by the input and only consider extra space required by the algorithm.
• Similar to time complexity, Big O notation is used to represent space complexity.
• If the auxiliary space used by algorithm remains constant as the input size changes, the space complexity is O(1), and so on.

Pointers to think after this blog:

1. Why O(1) is better than O(N)?