sorting - Really confused about Time Complexities -
i know how calculate bigo each algorithm , generally, how works. example, finding specific number in linked list o(n) because you're possibly having go through every input in linked list head tail. however, bigo mean in regards time? how come merge sort can run faster insertion sort though insertion sort has faster "time complexity"? please give me input, can understand. thankyou much.
have @ example:
lets have 2 algorithms a₁
, a₂
. same, first has complexity of Θ(n)
, second has complexity in Θ(n²)
. both algorithms have different running times. cannot calculate running time complexity, since depends on exact implementation, computer running on, things cannot see in complexity , other things. can predict change of running time complexity. lets change input length n
length 2n
, means double input length. running time should (nearly) double a₁
, should 4 times more a₂
, since (2n)² = 4n²
.
to address insertion sort vs merge sort example: complexity of insertion sort o(n²)
, complexity of merge sort o(n log n)
. merge sort has better complexity insertion sort , should run faster. maybe (for short lists) insertion sort runs faster merge sort, because merge sort has bigger constant factor hidden in big-o notation.
Comments
Post a Comment