Time Complexity - Recursive function - Two recursive calls, and double nested loop

Question

function T(int n) {
  int n1 = T((n-1)/4) 
  int n2 = T((n+1)/4) 

  int sum = 0 

  for i = 1 to n {
    for j = 1 to n {
      sum+=n1*i + n2*j
    }
  }
  return sum
}

T(n) = ?

Answer 1

I think the equation becomes,

T(n)=2T(n/4)+n^2;

By Master's Theorem:

T(n)=n^2;

Comments

Thank you Nithin for answering my question. I think the form of the T(n) is aT(n-b)+f(n), where a, b >0 and f(n) is in O (n^k). so, would you mind telling me why did you change the form?

---

there are 2 recursive calls and dividing by 4 is more dominant than just subtracting it by 1 so I thought we can ignore that.

---

Thank you so much Nithin for your clarification, I really appreciate it!

---

This is correct I guess.

Answer 2

The orange line is T(n) = O(n^2), The blue things are the origin data.

---

It should be O(n²⁾

If you have interest, c likely equals to 346252 for cn².

Why:

(1)   int n1 = T((n-1)/4)  costs O(logn) and make n1 = 1

(2) so  as n2

(3) two recursive calls cost O(n²) 

Therefore, O(n²) in total.

---

Image seems crash. here is the URL: https://github.com/wfgydbu/swap/blob/master/tt1.jpg

Answer 3

Here is my try, please let me know if it's correct or not.

T(n)= T(n-1) +  n²

Since the value of a= 1, then T(n) = O (n ^k+1)

This means that  T(n) = O(n³)

Comments

Hi Amal, why did you simplify the recursion into T(n) = T(n-1) + n^2?

---

@Amal - There seem to be two recursive calls of size n/4.

---

Hello Taoran,  forget my answer please :D
I wasn't sure about it.

---

Thank you Prof. Amrinder for answering my question.