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)

asked ago in Algorithms by Junior (945 points)
retagged ago by | 48 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?

Please log in or register to answer this question.

Related questions

0 votes
1 answer
asked Dec 30, 2018 in Algorithms by Rahul_Rathod_ Junior (565 points) | 30 views
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
48,411 questions
52,746 answers
68,213 users