# What is the Runtime of this recursive algorithm?

I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in recursive function.

my_func takes an array parameter 'A' of length n. Runtime of some_func() is constant.

def my_func(A):
if (n < 4):
some_func(); /* O(1) time */
else:
[G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each */
my_func([G1, G3]); /* recurses on size n/2 */
my_func([G1, G4]); /* recurses on size n/2 */
my_func([G2, G3]); /* recurses on size n/2 */
my_func([G2, G4]); /* recurses on size n/2 */
some_other_func(); /* split() and some_other_func() take O(n) time */


Questions

1. Can I say the asymptotic runtime of my_func is:

T(n) = 4T(n/2) + O(n), T(1) = O(1)

because my_func is called recursively 4 times for (n/2) size, then split is O(n) and some_other_func is O(n). The base case keeps T(1) = O(1)

1. What is the total number of steps performed by my_func(A)? I know that if there are nested for loops then simply multiply. How to calculate in this case? I was trying use Google search and it point to Omega(n^3). Is that correct?

Now what if I rewrite this function as:

def new_func(A): /* A is array of length n 8/
if (n < 4):
some_func(); /* O(1) time */
else:
[G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each
new_func([G1, G2]); /* recurses on size n/2  */
new_func([G2, G3]); /* recurses on size n/2  */
new_func([G3, G4]); /* recurses on size n/2  */
some_other_func(); /* split() and some_other_func() take O(n) time */


Questions:

1. What is the number of steps now?

I am thinking it will be omega(n^3)

1. Is new_func faster than nlog(n)?

I think no because Merge sort is T(n) = 2T(n/2) + n and new_func is T(n) = nT(n/2) + n

• There's something mixed up in ur writing, the 2nd with new_func() doesn't differ than above except for the recursive call is 3times (not 2 as u wrote in Q). In general, u could substituteT(n)= aT(n/b)+cn =⟩ T(n)=a[aT(n/b²)+c(n/b)]+cn, then work ur way out to logn to base b times (when u reach T(1) as n is divided to b^(logn base b) which equals n). Take care in here a=b², so a^(log n base b) = n²
– ShAr
Sep 27 '21 at 5:58

In my_func(a), Recurrence Relation will be

$$T(n) = \begin{cases} 4T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } n <4 \end{cases}$$

In new_func(a), Recurrence Relation will be

$$T(n) = \begin{cases} 3T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } n <4 \end{cases}$$

You can solve Both of these Recurrence Relations using Master Theorem as explained in link.

The Time Complexity of my_func(a) will be $$\theta(n^2)$$ since $$\log_24 = 2$$

The Time Complexity of new_func(a) will be $$\theta(n^{1.5849})$$ since $$\log_23 = 1.5849$$

You can solve both of these questions by Substitution Method, which is Time Consuming. One of the Example using this method is attached.

The new_func(a) will be slower than Merge Sort, and faster than my_func(a).