@Aanchal : My mistake... Its complexity can't be O(n^2)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Can someone please help me with finding the complexity of below code:
/*The code is of finding all possible combinations of coins (given in array,
each having infinite supply) that sum upto given target value.*/
void solve(int index[], int arr[], int target, int cursum, int n, int sz)
{
cnt++;
really sorry for that,
here is the complete code:
#includeiostream
using namespace std;
void print(int arr[], int index[], int n)
{
int i=1;
while(i=n)
{
coutarr[index[i]] ;
i++;
}
coutendl;
}
void solve(int index[], int arr[], int target, int cursum, int n, int sz)
{
Its complexity is same as of finding the all combination if a given string .
it is O(n!)
--
*With Regards :*
Ravinder Kumar
B.Tech Final Year
Computer Science and Engineering
MNNIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
Can we prove this??
On Wed, Aug 3, 2011 at 1:45 AM, Ravinder Kumar ravinde...@gmail.com wrote:
Its complexity is same as of finding the all combination if a given string
.
it is O(n!)
--
*With Regards :*
Ravinder Kumar
B.Tech Final Year
Computer Science and Engineering
MNNIT
I was asked a similar question in an interview, and the interviwer told me
that it is O(n^2), I have no idea how he got that!!
On Wed, Aug 3, 2011 at 1:47 AM, aanchal goyal goyal.aanch...@gmail.comwrote:
Can we prove this??
On Wed, Aug 3, 2011 at 1:45 AM, Ravinder Kumar
My mistake .I only saw the program flow which is similar to
permutation .
Its DP similar to 0,1 knapsack
Complexity is O(nc)
where c is size of knapsack
and n is number different of items
--
*With Regards :*
Ravinder Kumar
B.Tech Final Year
Computer Science and Engineering
MNNIT
But this is not dp rite? I know knapsack problem, it has 2 nested for loops,
thats why it is O(nc). And also, here we have infinite supply of each item.
And we want all possible ways of getting the sum, not just one way.
Here, function is recursively called, like a dfs is performed here... So,
it depends on target sum .
Size of index array is depends on target sum .
Try to dry run it you will get hint .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe
@Ravinder : Its not a DP problem.. If it was, where are the sub problems
reused or in other words, where is memoization ??
@Anchal : Its complexity is O(n^2). Look at the following segment in ur code
:
for(int i=index[n];isz;i++)
{
index[n+1]=i;
let sum=45
int arr[]={1,2,3,4,5}; /*43545 times the function solve is called*/
/*2611 ways of achieving the sum (2611 ways will
be printed)*/
if,
int arr[]={1,3,10,30,75}; /*2931 times the function solve is called*/
/*53 ways of
@ Ankit Sambyal,
please explain me why is it O(n^2) taking into account what the number of
times solve is called (in my example above.)
On Wed, Aug 3, 2011 at 10:36 AM, aanchal goyal goyal.aanch...@gmail.comwrote:
let sum=45
int arr[]={1,2,3,4,5}; /*43545 times the function solve is called*/
sorry, *target=45*, not sum. sum=0 when we call the function the first time.
On Wed, Aug 3, 2011 at 10:39 AM, aanchal goyal goyal.aanch...@gmail.comwrote:
@ Ankit Sambyal,
please explain me why is it O(n^2) taking into account what the number of
times solve is called (in my example above.)
Running time can be found by solving this recursion.
T(sz,target) = SUM {1=i=sz} T(i,target-1)
T(sz,0) = c
I think it is around O(sz^target)
Thanks
Nitin
On Wed, Aug 3, 2011 at 10:40 AM, aanchal goyal goyal.aanch...@gmail.comwrote:
sorry, *target=45*, not sum. sum=0 when we call the function
fun(n)
{
if(n=2)
return (1);
else
return ((fun(n-1)*fun(n-2));
}
find the order of complexity .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group,
O(2^n)
On Sat, Jan 22, 2011 at 8:58 PM, Decipher ankurseth...@gmail.com wrote:
fun(n)
{
if(n=2)
return (1);
else
return ((fun(n-1)*fun(n-2));
}
find the order of complexity .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
Could u pls explain ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
T(n) = T(n-1) + T(n-2) + O(1)
On Sat, Jan 22, 2011 at 11:28 PM, Decipher ankurseth...@gmail.com wrote:
Could u pls explain ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
18 matches
Mail list logo
