If we traverse the entire linked list(say singly linked list) 1st time then time complexity asymptotically comes O(n)[where n is the no. of element present] same thing if we repeat it significant no. (say 200) of time but still we represent time complexity O(n) itself then My Question is 1.Why we are not considering the difference between the above(because second one will take more time to traverse than first one)and we represent it same asymptotically.As we use time complexity major parameter to make comparison between Algorithms.
Asked
Active
Viewed 198 times
0
-
3Possible duplicate of [Why do we ignore co-efficients in Big O notation?](https://stackoverflow.com/questions/29954109/why-do-we-ignore-co-efficients-in-big-o-notation) – rob mayoff May 23 '18 at 02:41
2 Answers
0
Let's say algorithm A is "traverse the list one time".
Let's say algorithm B is "traverse the list 200 times".
They are both linear, that is, their time complexity is in O(n). Why? If you double the size of the input list,
- algorithm A takes twice as long as it did before.
- algorithm B takes twice as long as it did before.
That is the intuition behind linear time.
You can always plug in the formal definition of Big-O to prove that "traversing a list 200 times" is linear in complexity (you know, find a constant k such that for all n > some N, blah blah blah). Asymptotic complexity only cares about how a particular algorithm behaves when the size of its input grows. So we don't need to compare algorithm A with algorithm B to say anything about the asymptotic time complexity of algorithm B.
Ray Toal
- 86,166
- 18
- 182
- 232
0
O(n) provides for the upper limits the maximum time a function can take hence maybe they both are taking different times but their upper limit remains the same.Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
Nikhil S
- 3,786
- 4
- 18
- 32