Forem: Madhav Gupta

Understanding the time complexity in a simple manner(Part 1) || DSA || prerequisite

Madhav Gupta — Thu, 04 Feb 2021 04:35:15 +0000

Hello Everyone, I hope you are all safe and in good health.

This is Madhav Gupta and today I'm here to throw some light over finding time complexities of algorithms. This can also be taken as a prerequisite for my upcoming DSA(data structures and algorithms) articles which I'll be writing in the coming future.

All of us face the questions of complexity in our interviews and we should know in general how to find complexities because it makes us a better engineer.

Now let's focus because

So coming on to the point, there are some rules which you should keep in mind while finding complexity of the given algorithms and these are -

Ignore constants.
Take the biggest degree in the expression formed.
Break your code into segments and analyse them one by one.

Also, there's one thing which we need to keep in mind, n is significantly large in our case for which we find time complexity.

Let's talk about statements which take linear time.

Declarations and operations - These are the statements which always take linear time and examples of some of them are



int x=0
x=x+1
x=x-1
x=x*4

All of the above statements if executed independently would run in O(1) time.

After talking about the statements that execute in linear time, let's talk about loops. I can already find it getting exciting and more challenging as we progress through the article.

Loops - Now things start changing from here, because iterations gets repeated and time complexity here is equal to number of times the loop ran. Let's look at the following code - ```

for(int i=0;i<n;i++){
a=a+2;
}

So, if we try to find how many times the statement *a=a+2* executed, we would get that *a=a+2* executed n number of times.
Suppose if statement *a=a+2* is taking k seconds to execute(k is constant), then our time function here would be 
T(n) = kn.
That would give us time complexity as **O(n)**.

Let's take various instances in loops and let's analyse them one by one.

---

for(int i=n;i>0;i--){
print("*");
}

In the above case, now i is n in the starting and it is decreasing by one. The loop stops but when i becomes 0.

The main thing to analyse here is that even if our i is decreasing, the number of iterations remain the same. Hence this loop is also having the time complexity of **O(n)**.

---

for(int i=1;i<=n;i=i+2){
print("*");
}

In the above case,i is increasing at the rate of 2. That means the time function here would look something like this

T(n)=n/2 
As we know we have to take only the biggest degree in our expression. Hence the above for loop would take time complexity as **O(n)**.
Even if i is increasing at a rate of 20, the time complexity of would remain the same.

___

for(int i=1;i<n;i=i*2){
print("*");
}

Now here the case is different. Here i is multiplying itself with 2. Let's look at the value of i with every iteration.

|Iteration|i|
|:----|:----|
|1|1|
|2|2|
|3|4|
|.|.|

Let's suppose the loop ends at the k-ith iteration, so the value of i at k-ith iteration would be 2<sup>k</sup>.

2<sup>k</sup>=n
Taking log both sides,
k=log<sub>2</sub>n

Hence the time complexity in this case would be **O(log<sub>2</sub>n)**. The same would be the case when i starts with n(loop ends at 1) and it keeps itself dividing by 2.

___

for(int i=0;i*i<n;i++){
print("*");
}

Here the case is that when i*i i.e. i<sup>2</sup> would become equal to n, then the loop would stop.
So let's assume the loop stops at i=k.
So, k*k = n
k<sup>2</sup> = n
k = <span>&#8730;n</span>

Hence the time complexity in this case would be <b>O(<span>&#8730;n</span>)</b>

I know it might feel boring at first but it's really necessary to understand how it all works under the hood. Otherwise, all of us can memorise that the time complexity of selection sort is O(n<sup>2</sup>). But we should also understand how it came there in the first place.

Now comes the most important instance in for loops.

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print("*");
}
}

Let's analyse the above loop first, how many times the statement `print("*")` would execute. For i=1 the inner loop would execute n times, for i = 2 the inner loop would execute n times again and for i = n, the inner loop would execute n times.
Hence the total number of times the statement `print("*")` got executed = n+n+n+..n times
T(n) = n(1+1+1+..n times)
T(n) = n * n
T(n) = n<sup>2</sup>
Hence the time complexity for nested for loops is **O(n<sup>2</sup>)**
___

While we were at it, we have completed our loops part already. I congratulate you for making it this far. Give yourselves a pat on your back and let's talk about if-else block.

___

* If-else statement - We take the time complexity of the block for whichever it is larger. The following example would clear it out.

// Time complexity = O(1)
if(i==0){
print("");
}
// Time complexity = O(n)
else{
for(int i=0;i<n;i++){
print("");
}
}

As we can see in the above code that if block is having O(1) and else block is having O(n). Hence the time complexity of the whole if-else block would be **O(n)**(since O(n)>O(1)).

___

* Consecutive Statements - We add the time complexities of each statement. Here's is an example

// takes O(1) time
int m=0;

// takes O(n) time
for(int j=1;j<=n;j++){
print("*");
}

// takes O(n^2) time
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print("*");
}
}

Taking into consideration the constant time of each print statement too.
Total cost = c<sub>0</sub>+c<sub>1</sub>n+c<sub>2</sub>n<sup>2</sup>
Taking the biggest degree, 
Hence time complexity = **O(n<sup>2</sup>)**

___

Phewww, That was really a long article, wasn't it? 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4pfgsculv9wg2uflqzxe.gif)

With that being said, it really feels good to be writing again. In this article i explained all the basics we need to find time complexities for common algorithms. I'd be bringing part 2 of the same topic with lots of questions which we would practice together and it would further strengthen our understanding.

I would attach the link of part 2 whenever i post the next part so be sure to save this one. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/yrt24z34nictggla9fyy.gif)

Please let me know if you liked this one or not, I'd gladly accept any criticism that comes my way and return with better content.

A comprehensive guide on markdown

Madhav Gupta — Wed, 06 Mar 2019 22:16:54 +0000

Hello everyone. Hope you are doing great.
I am Madhav Gupta and this post will be dedicated to markdown.
By the end of this post, I really hope that you'll be having more than enough knowledge of markdown to use it in your daily life.

Let's start with a bunch of questions,

Q- What is Markdown?
A- Markdown is a lightweight markup language with plain text formatting syntax. In simple terms, markdown is a way to style text on the web having simple syntax than HTML.

Q- Why bother learning it?
A- There can be a lot of reasons to learn Markdown, I will be listing some of them

Easy to learn and easy to read
Used in Github documentation
can be easily converted into other formats
you might start writing posts on dev.to after learning it

Enough with the questions, let's get on board.

Headers

There are six types of headings ranging from H1 to H6. You can use headers in two ways.
First - Using a # followed by the text
Second - Inserting 3 ===(for H1) or ---(for H2) below the text. The downside of going through this path is that you can only use H1 and H2. Hence I'll recommend sticking to the former way.

Examples -

# H1
## H2
### H3
#### H4
##### H5
###### H6

(spaces given for readability)

H1

H2

H3

H4

H5

H6

H1
===

H1

H2
---

H2

Text Formatting

Formatting text in markdown is very easy. You can change the feel and look of your text by making it italic, bold or ~~striking it~~.

Examples -

_italic_ or *italic*

italic

__bold__ or **bold**

bold

~~strikethrough~~

~~strikethrough~~

Since there are two ways for text to be italic and bold. So in order to avoid the confusion, I will recommend using italic and Bold. This will help you in reducing the ambiguity and confusion you might face while styling your text.

Lists

You always make lists for one purpose or another. You can use both unordered and ordered lists in markdown according to your needs

Unordered Lists
Here is the syntax for an unordered list in markdown. You can replace + with * or -

+ First item in the unordered list
+ Another item in the unordered list
+ one more item

Above code gets converted into this.

First item in the unordered list
Another item in the unordered list
one more item

Ordered Lists

1. The first item in the ordered list
2. The second item in the ordered list
3. The third item in the ordered list

Instead of going with the above syntax, you can also go with

1. The first item in the ordered list
1. The second item in the ordered list
1. The third item in the ordered list

and both the examples will result in the following list

The first item in the ordered list
The second item in the ordered list
The third item in the ordered list

Links

You can use links in markdown by using the following syntax.

[Text](the link you want to relate with text)

Example -

[Link to my first article](https://dev.to/madhavgupta/visual-studio-code-and-its-magic-1a2m)

Link to my first article

Both ways can be used to reference external links but I will recommend the latter one for enhanced readability. Instead of using [1], you can use anything such as [meow] or [blah] and it will work fine.
If there is no text, then you can highlight the link be using <link>.

Images

Images can be embedded in a markdown document by using the following syntax. Not only images, but you can also use gifs too by using the same syntax.

![Alt text for your image](Link of the image)

Example -

![](https://images.unsplash.com/photo-1515524738708-327f6b0037a7?ixlib=rb-1.2.1&ixid=eyJhcHBfaWQiOjEyMDd9&auto=format&fit=crop&w=1050&q=80)

Horizontal Rule

Depending on how your parser makes the horizontal rule, it is always great to have some of them in your article/documentation.

Example-

--- or *** or ___

Code block

Add code blocks to your posts/articles by surrounding your code with three
backticks and if you want to highlight syntax, then write the name of language after backticks.

Block Quote

Give special emphasis to the quotes to make them stand out.

> Quote

Example -

> “Websites promote you 24/7: No employee will do that.” 
― Paul Cookson

“Websites promote you 24/7: No employee will do that.”
― Paul Cookson

Tables

Showing data in tabular form is very convenient and I must say, making tables in markdown is not so pretty. One more thing, the : is responsible for the alignment of the elements in rows. Examples given below will make this statement more clear.

|Songs|Creators|
|:-----|:-----|
|Without Me|Helsey, Khalid and Benny Blanco|
|Hope|Chainsmokers|
|Never Gonna give you up|_I'll leave it here_|

Songs	Creators
Without Me	Helsey, Khalid and Benny Blanco
Hope	Chainsmokers
Never Gonna give you up	I'll leave it here

|Songs|Creators|
|-----:|:-----|
|Without Me|Helsey, Khalid and Benny Blanco|
|Hope|Chainsmokers|
|Never Gonna give you up|_I'll leave it here_|

Songs	Creators
Without Me	Helsey, Khalid and Benny Blanco
Hope	Chainsmokers
Never Gonna give you up	I'll leave it here

You can also use the good-old HTML tags(pre, code, img, table) in markdown if you ever feel the need to. Markdown is great and it makes sure that your entire focus remains on the content.

If you knew it all, congratulations. This post might act as a refresher for you. If it is the other way around, Hope it helps.

So, that's it for today. I'll be back soon with another one(open for ideas).
Hope you like it.
Have a great day. Thanks.

Visual Studio Code and its magic

Madhav Gupta — Sun, 03 Mar 2019 21:52:18 +0000

Hello, I am Madhav Gupta(someone who's been using VS Code for a long time sufficient to fall in love with it) and I'd like to walk you through the amazing world of shortcuts in VS Code and a wonderful extension.

We all love studio code, don't we? (talking about those who use it)

At my starting point, I always wondered how the tutor was able to move a selection up without moving the mouse, copy a whole selection and move it down simultaneously. Turns out these were the key shortcuts who were the culprits all along.

So coming on to the point,
Being a developer, you sure know one thing that mouse is wicked for you. You should be familiar with most of the key shortcuts available in your editor.

While there are so many shortcuts available in the editor, I will be listing some of the shortcuts I use the most. As a side note, you can find the full list of keyboard shortcuts here.
These are for windows users, so please excuse me if you use any other OS.

Here's a table for the shortcuts and what they do.

Keyboard Shortcut	Their effects
Alt+ ↑ / ↓	Move your selection up or down
Shift+Alt + ↓ / ↑	Copy your selection and move it up or down
Ctrl+ ] / [	Indent/Outdent Line(move your selection left or right,in simple words)
Ctrl+Shift+\	Jump to matching bracket
Ctrl+↑ / ↓	Scroll your selection UP or Down
Ctrl+/	Toggle comment (uncomment a selection if commented & vice versa)

While these are shortcuts which I tend to use most of the times, Some of the honorable mentions are,

Keyboard Shortcut	Their effects
Ctrl+Space	Shows you all the recommendations when coding/Trigger suggestion
Ctrl+. (Credits- Michael De Abreu)	Quick fix
Ctrl+P(Credits- Đào Tuấn)	Open any file in your root folder
Ctrl+F	Find
Ctrl + H	Replace
F11	Toggle Full Screen
F5	Start debugging
F9	Toggle Breakpoint
Ctrl+Shift+T	Reopen closed editor

So these were some of the most used keyboard shortcuts, besides Ctrl+C & Ctrl+V of course 😀😀
If you knew them all and use them, Congratulations. Be sure to share some of the shortcuts which you use all the time in comments.

Now, let's talk about the extension.

The name of the extension is JavaScript (ES6) code snippets

People who use it know the power of this extension. As the name depicts, this extension provides you code snippets with some shortcuts and you can use them by hitting TAB or ENTER.

Shortcut	What it becomes into
clg	console.log()
thenc	Then and catch chained `.then((res) => {}).catch((err) => {});`
imp	imports entire module
rqr	Require
mde	module.exports()
con	adds default constructor in the class `constructor() {}`
fre	forEach loop in ES6 syntax `array.forEach(currentItem => {})`

So, that's it for today. Pheww, writing my first post was not that tough.
I'll be back with more posts( Thinking to write a guide on markdown) and one more thing, No hate on other editors, Just use what fits you.
Hope you like it. Have a great day. Thanks.
Edit : grammatical fix