What is the running time of this Haskell merge code

Question

I came up with this code which takes two SORTED in ascending order lists and then merges those two lists into one single list, preserving the ascending order-sortedness. I was trying to analyze it and see what the time complexity of it is. My belief is that in the worst case, we will have to traverse through the whole lists and since there are 2 lists we're gonna have to have a nested recurence, which means O(n^2) time for the WORST case. However, since we're comparing the sizes of each of the two elements before we recurse, I am thinking that this is probably O(log n) time. Correct me if I'm wrong please. Thanks

Here's my recursion:

mergeLists::[Integer]->[Integer]->[Integer]
mergeLists [] []        =[]
mergeLists [] (y:ys)    =(y:ys)
mergeLists (x:xs) []    =(x:xs)

mergeLists (x:xs) (y:ys)
 |(x<y)                 =x:mergeLists xs (y:ys)
 |otherwise             =y:mergeLists (x:xs) ys

it is usually defined as left-biased, i.e. when x==y, then pull x, not y: `| y>x = y : ...`. — Will Ness, Oct 14 '14 at 10:36

score 2 · Answer 1 · answered Oct 14 '14 at 01:38

2

as the listed is already sorted .. then the merging time will be O(n) while n is the total size of the two lists.

it will work like the merge sort : http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html

answered Oct 14 '14 at 01:38

Kareem Hashem

1,057
1
9
25

score 2 · Accepted Answer · edited May 23 '17 at 11:43

The time efficiency will be O(n), since the two lists are presumed to be in ascending order already. You don't need to recurse or perform any part of a comparison more than the number of elements in each list passed to the function.

Ach, Kareem already answered the question. I'll make it better by providing an understanding of Big-O notation for time and space efficiency. Big-O Notation is used to represent a basic concept of algorithmic performance over a set of data of arbitrary size. It's obvious that with an increasing data set for an algorithm to work on, the actual time to perform the operation increases. If the increase in time is determined linearly (IE each data member increases the algorithms actual time to finish by an equal amount as all other elements), then the algorithm's time efficiency is said to be "on the Order of n" or O(n). This is the case with your algorithm.

To learn more about Big-O notation, a great read is on another question here on StackOverflow: What does O(log n) mean exactly?

score 1 · Answer 3 · answered Oct 14 '14 at 07:07

Your mergeLists will take O(n+m) where n and m are the lengths of the input list. This can be easily proved by mathematical induction on n+m that the number of recursive calls will be at most n+m.

For the first 3 cases, there is no recursion, so the number of recursive calls is trivially less than n+m.
For the last 2 cases: In each case, the nested call receives one of the original lists and the other shortened by 1. So we can use the induction principle which tells us that the nested call will make at most n+m-1 recursive calls, and so the call in question will make at most n+m calls.

What is the running time of this Haskell merge code

3 Answers3