Time complexity

Question

Is this the correct way to solve ?

Q) int algorithm(int n)
{
   int sum =0;k,j;
   for (k=0;k<n/2;k++)
      for(j=0;j<10;j++)
          sum++;
  return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2)
}

Comments

By the for loops ==> 10.$\frac{n}{2}$ ===> C$_1$.$\frac{n}{2}$.

$\text{return 4}*\color{red}{\text{algorithm}(\frac{n}{2})}*\color{green}{\text{algorithm}(\frac{n}{2})}+\color{magenta}{\text{algorithm}(\frac{n}{2})}*\color{blue}{\text{algorithm}(\frac{n}{2})} $

Total four times(red,blue,green,magenta) you are recalling the original problem with the size of half of input.

Note that, the return value is different, and the calls are different.

Totally ===> T(n) = C$_1$.$\frac{n}{2}$ + 4.T($\frac{n}{2}$) = 4.T($\frac{n}{2}$) + n

---

you have written $4T(n/2)*T(n/2)$ for 4*algorithm(n/2)*algorithm(n/2) but 4*algorithm(n/2)*algorithm(n/2) means multiply the return value of algorithm(n/2) by 4 and then again multiply it with return value of algorithm(n/2). * is used for multiplication. if you write 4T(n/2) it means we are calling algorithm(n/2) 4 times , here "4" does not mean we are multiplying by 4 in return value of algorithm(n/2).

Here, 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) involves 3 multiplication and 1 addition operation which are of constant cost i.e. O(1) for each function call and here overall we are calling algorithm(n/2) 4 times and O(n/2) extra cost due to loops in the code.

So, Recurrence relation for the above code can be written as :-

$T(n) = 4T(n/2) + O(n)$

---

$T(n)=4*T(n/2)*T(n/2)+ T(n/2)*T(n/2) + 10*O(n/2))\\ T(n)=(T(n/2)^{2})(4+1) + O(n)\\ T(n)=5T(n/2)^{2} + O(n)$

Why the expression isn't like the one above?

---

time complexity means howmany times the sub problems are recursively called...

after that, you will multiply them for returning the value which takes o(1) times.

---

Thanks, got it.. :)

---

@Shaik Masthan now my doubt is clear, thanks a lot

---

@Shaik Masthan,Bhai but in above example the code has been used 3 times. However,since 4*T(n/2) has been mentioned therefore,the code used 4 times. Am I right?

---

noo brother, read one more time the previous comments !

is it 3 times or 4 times used check ome more time ?