A simpler way to understand time complexity in algorithms

Meet Zaveri — Thu, 28 Mar 2019 13:16:45 +0000

Understanding it with array and object as a data structure

Let's analyze time complexity for finding a value from a data structure,

Suppose a data structure would be an array. So to find a value in array, you might have to traverse through array to find a value.

Worst time complexity : O(n)

Best time complexity : O(1)

Here O(n) means it will iterate through all elements in an array of size n. O(1) in a nutshell, means regardless of size of array(i.e. input provided), we can find value on one attempt.

Instead if a data structure would be an object or hashmap, we could find value directly by knowing it's key assigned to it. So here time complexity would be constant as O(1)

Time complexity : O(1)

Operations in an Array

INSERT (PUSH): Insert operation in array would take O(1) runtime to push data into array as it knows it has to push at last index of an array.

DELETE (POP): It's best runtime would be same as insert operation it will take O(1) if we want to delete from beginning or at the end of the collection.

But if we want to delete item in middle of the collection, it's runtime would be O(n)

Analogy for it!

A lot of students get confused while understanding the concept of time-complexity, but in this article, we will explain it with a very simple example:

Imagine a classroom of 100 students in which you gave your pen to one person. Now, you want that pen. Here are some ways to find the pen and what the O order is.

O(n2): You go and ask the first person of the class, if he has the pen. Also, you ask this person about other 99 people in the classroom if they have that pen and so on,
This is what we call O(n2).

O(n): Going and asking each student individually is O(N).

O(log n): Now I divide the class into two groups, then ask: “Is it on the left side, or the right side of the classroom?” Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n).

That's it, thanks for reading guys!

I wondered how async module works, so I made some functions and hosted on npm

Meet Zaveri — Fri, 24 Aug 2018 08:54:26 +0000

Since I have been in node.js development, I used caolan's async module very often. They provide best collections to boost productivity in development for APIs.

One day I was like wondering on my desk that how this async.auto() or async.parallel() works so flawlessly. Also I was curious and wanted to know how would be picture behind this like function compositions, callback implementation and handling iteration for series control flow.

I started trying to implement few of them, though didn't accomplished more sophisticated approach like caolan's. I did refactoring and maintained only few of them and limited to mainstream/common control flow methods.

Tested all of it, though need more use cases to find issues but still it's working when I made it out of a litte sandbox.

Motivation - Curious about async and wanted to take out more from beautiful callbacks.
Github - https://github.com/meetzaveri/elite-set-of-async-utilities
NPM - https://www.npmjs.com/package/vanilla-async

Feedback appreciated much more !

DEV Community: Meet Zaveri

A simpler way to understand time complexity in algorithms

Understanding it with array and object as a data structure

Operations in an Array

Analogy for it!

I wondered how async module works, so I made some functions and hosted on npm