in Algorithms
2,577 views
1 vote
1 vote
In Merge sort Algorithm when I took input array of size 2 and I got 4 function calls as including original function call with which I call MS algorithm i.e. MS (1,2) and which in turn calls two recursive function calls to merge sort as MS (1,1) and MS (2,2) and one function call to merge procedure as Merge (1,1,2)


Likewise for input array of size 3 I got 7 function calls.

for input array of size 6 I got 16 function calls.
So, how can I analyze the total number of function calls when input array size is n?


thank you!
in Algorithms
by
2.6k views

4 Answers

4 votes
4 votes
For Merge Sort

no of times Merge Sort called = $2n - 1$

no of times merge is called = $n-1$

1 comment

for input array of size 6 I got 16 function calls.
0
0
1 vote
1 vote
For ‘Merge-sort’ the number of function calls can be represented by T(n)

$T(n)=2T(\frac{n}{2})+2$, and T(2)=2

Solving which we get 2n-2, we add 1 for call from the main function, therefore (2n-1).

SImilarly for ‘Merge’ function

$T(n)=2T(\frac{n}{2})+1$ and T(2)=1

Which comes out to be (n-1).
0 votes
0 votes

for n=2    4 calls

for n=3    7 calls

for n=6     16 calls

thus for “n” calls “3n-2” calls

0 votes
0 votes

Total number of MERGESORT() calls = 2n-1

Total number of RECURSIVE MERGESORT() calls = 2n-2 (The very first call will not be a recursive call)

Total number of MERGE() calls = n-1