Linear Time Complexity O(n) only works for Direct access from any DS (like: List, Dict, Linked List or Tree etc.)
If you are searching for an Element going through each one, then the Time Complexity will become O(n).
Because you are checking all elements one by one so,
For 1 Element = O * 1
For 2 Element = O * 2
For 3 Element = O * 3
For n Element = O * n
And Time Complexity = O * n = O(n)
(N.B.- 'O' is Growth Rate, we thought that as constant which is 1 second, And 'n' is Input Size.)
Constant Time Complexity O(1) only works for Direct access from any DS (like: List, Dict, Linked List or Tree etc.)
For direct access Input Size 'n' doesn't matter. That's why, we already know the index or location of the Element. So it takes only 1 second = 'O' Growth Rate Only.
It doesn't have to loop or check throw the Database or List. So, 'n' doesn't matter for Constant Time Complexity. So, here Time Complexity = O * 1 = O(1)
Quadratic Time Complexity = O * n^2 = O(n^2) works for Nested Loops (like: for Loop, while loop)
For nested loops Quadratic Time Complexity is applicable.
That's why In Nested loop for one Element we have to check the sub Elements of that Element.
So, for 'n' numbers of Elements you have to check 'n' numbers of sub Elements
0 Comments