What is the Runtime of this recursive algorithm?

Question

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) \text{ with } 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)$

2. 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 guess it will be $\Omega(n^3)$

2. Is new_func faster than $n\log(n)?$
   I think no because Merge sort is $T(n) = 2T(n/2) + n$ and new_func is $T(n) = nT(n/2) + n$

Answer 1

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).