I have the following pseudocode to figure out the approximate running time of. Anyone able to help but please explain each step and reason. thanks in advance
int m = n; while (m > 0) for k= 1 to m //dowork ---- CONSTANT m = floor(m/2)
Another Algorithm I would appreciate a break down of please. How would I compute the running time of this algorithm?
NB. This is taken from the wiki site writeup on merge sort but since that did not help, I was wondering if someone here would help break it down so I get where the O (n log n) comes from, for both best case and worst case.
function merge_sort(m) if length(m) ≤ 1 return m var list left, right, result var integer middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result
function merge(left,right) var list result while length(left) > 0 or length(right) > 0 if length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) else if length(left) > 0 append first(left) to result left = rest(left) else if length(right) > 0 append first(right) to result right = rest(right) end while return result