0

Here is my code for the sorting the list in ascending order. I have used function within the function. Now I want to calculate the Time complexity of this function. From my side I have calculate that the function "unite" is called every time when function "sort" complete its loop. So two functions are used every time in this function. So I have concluded that the Complexity of this function is O(nlog(n)). I am new to this chapter. So I want to know how to calculate this type of complexity. The answer above is just my approximation. And neither I know the real answer nor I have any solution or hints. So please describe your answer whenever you give. Thanks. Here is my code.

def sort(lst):
    def unite(l1, l2):
        if len(l1) == 0:
            return l2
        elif len(l2) == 0:
            return l1
        elif l1[0] < l2[0]:
            return [l1[0]] + unite(l1[1:], l2)
        else:
            return [l2[0]] + unite(l1, l2[1:])

    if len(lst) == 0 or len(lst) == 1:
        return lst
    else:
        front = sort(lst[:len(lst)/2])
        back = sort(lst[len(lst)/2:])

        L = lst[:]  # the next 3 questions below refer to this line
        return unite(front, back)
Improve this question
6
  • Whence cometh sort4? Commented Dec 12, 2013 at 19:44
  • Actually, it's at least O(n^2) because unite makes O(n^2) copies for inputs of size n1 + n2 = n. (And O(n log n) is not an approximation of that in any sense of the word.) Commented Dec 12, 2013 at 19:45
  • Oh but I have see couple of examples which have function calls with in the function. And they have the complexity of O(log(n)). Commented Dec 12, 2013 at 19:48
  • 1
    Just because you have function calls in a function doesn't mean that they're the same complexity as your examples. Runtime is based on what the functions do, not where they're constructed. There is a way to write your unite function that will allow it to run in O(n), but you didn't do that. Commented Dec 12, 2013 at 19:51
  • You might benefit from reading some of the other questions (especially the high-voted ones) with the tags time-complexity and/or big-o. Commented Dec 12, 2013 at 19:56

3 Answers 3

Reset to default
1

First step is to note that the real work is being done in the unite step of your code, which does n^2 work because you're creating new lists every time.

So you can actually write a quick recurrence for the amount of work your function is doing:

W(n) = 2W(n/2) + n^2

because you're recursing twice on lists that are of length n/2 and doing n^2 work to rejoin them.

Now, consider a recursion tree - at a certain level of the tree (call it level i), you're doing 2^i * (n/2^i)^2 work. That's about O(n^2) work at each level, and there's log(n) levels, so you're doing O(n^2log(n)) work.

However, there is a way to write your unite function so it runs much faster, in O(n) time. In that case, you'd be doing (by a similar analysis as above) O(nlog(n)) work.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

No. n^2 is not the correct answer. Still I do not have any answer.
0

The time for sort to execute on an n-element vector is T(n).

T(n) =  2 T(n/2) + n

     =  2 [2 T(n/4) + n/2] + n

     =  4 T(n/4) + 2n

     = 4 [2 T(n/8) + n/4] + 2n

     = 8 T(n/8) + 3n
     ........

     = 2k T(n/2k) + k n

     = 2log2 n T(1) + (log2n) n   because T(1)=O(1) 

     = n + n log2 n    

     = O(n log n)

There is an easy way to remember the complexity for sort solution recursive function. T(selection sort) = O(n^2), and T(merge sort) = O(nlogn). Obviously, your code is merge sort type.

Improve this answer

Comments

0

Time Complexity (not space complexity) of above code is O(nlog(n)).

There are n elements in the list at start and we recursively divide that list in n/2 elements every time into front and back which makes it O(log(n)) steps. Now, for each of O(log(n)) steps we iterate over each element in l1 and l2 in unite function only once which makes complexity of unite function O(n).

Hence, for O(log(n)) divisions and O(n) unite steps makes this algorithm O(nlog(n)) of time complexity.

Other answers are discussing about space complexity of unite function which is O(n^2), but question title clearly asks about time complexity and not about space complexity.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.