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)
O(n) means it will iterate through all elements in an array of size
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)
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
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!