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

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

asked ago in Algorithms by Junior (945 points)
retagged ago by | 48 views
+2

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

+2
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)$
0
$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?
+2
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.
0
Thanks, got it.. :)
+1

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

0

@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
2
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
183,341 comments
68,213 users