Time complexity of insertion Sort
To
compute the runtime, it is quite easy when we realise that we run through each
of the elements in the array and so, the runtime is a function of the number of
elements, n. Further we notice that for each of the n elements when we take it,
we move to the left, element by element making comparisons which at worst case,
is that we run through n-1 elements which is approximately another n.
Thus,
Total runtime= O(n×n) = O(n^2)
No comments:
Post a Comment