The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

Is this the correct way to solve ?

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

in Algorithms by Junior (801 points)
retagged by | 133 views

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 ?

Please log in or register to answer this question.

Related questions

0 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,729 answers
79,937 users