Re: [algogeeks] Complexity

[Durgesh Kumar]

saurabh is right nd or U can also download lecture 2  of series "
Introduction to Algorithm mit lecture" . It is jst awesome .

On 12/15/11, saurabh singh  wrote:
> Introduction to Algorithms Coreman
>
> On Wed, Dec 14, 2011 at 8:21 PM, Shashank Jain  wrote:
>
>> I need to study both space and time complexities. What is the best source?
>>
>> --
>> 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, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
*Durgesh Kumar*
Final Year, B.tech
Information Technology
HALDIA INSTITUTE OF TCHNOLOGY
HALDIA

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity

[saurabh singh]

Introduction to Algorithms Coreman

On Wed, Dec 14, 2011 at 8:21 PM, Shashank Jain  wrote:

> I need to study both space and time complexities. What is the best source?
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] complexity of recursion

[shady]

it is O(n)
actually we use memoization in recursion to avoid calculating same
subproblem.

On Wed, Sep 14, 2011 at 9:38 PM, tech coder wrote:

>
> an interseting problem
>
> for a fibonacci series
> the recurrence relation is
> t(n)=t(n-1)+t(n-2)+O(1)
> on solving it gives upper bound of O(n^2)
>
> but when draw tree for the recurcsion we see that it is growing
> exponentially giving a complexity of O(2^n).
>
> so what is the complexity for fibonaacci series n^2 or 2^n
>
> --
> *
>
>  Regards*
> *"The Coder"*
>
> *"Life is a Game. The more u play, the more u win, the more u win , the
> more successfully u play"*
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[ankit sambyal]

@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 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[Nitin Nizhawan]

SUM {0<=i<=target} C(sz+i-1,i)

  O(2^(sz+target-1))

Thanks
Nitin
On Wed, Aug 3, 2011 at 11:03 AM, Nitin Nizhawan wrote:

> 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 
> wrote:
>
>> 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 
>> wrote:
>>
>>> @ 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 >> > wrote:
>>>
 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 achieving the sum*/


 So, ho here n=5, but see how many times the solve function is called! if
 it was n^2, then it would have been called just 25 times

 On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal 
 wrote:

> @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];i  {
>   index[n+1]=i;
>   solve(index,arr,target,cursum+arr[i],n+1,sz);
>  }
>
> Here sz is the number of elements in the array i.e. n for complexity.
> There is a recursive call to solve ..
> I hope its clear now .
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



 --
 Regards,*
 Aanchal Goyal*.


>>>
>>>
>>> --
>>> Regards,*
>>> Aanchal Goyal*.
>>>
>>>
>>
>>
>> --
>> Regards,*
>> Aanchal Goyal*.
>>
>>  --
>> 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, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[Nitin Nizhawan]

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 wrote:

> 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 
> wrote:
>
>> @ 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 
>> wrote:
>>
>>> 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 achieving the sum*/
>>>
>>>
>>> So, ho here n=5, but see how many times the solve function is called! if
>>> it was n^2, then it would have been called just 25 times
>>>
>>> On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal wrote:
>>>
 @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];i>>>  {
   index[n+1]=i;
   solve(index,arr,target,cursum+arr[i],n+1,sz);
  }

 Here sz is the number of elements in the array i.e. n for complexity.
 There is a recursive call to solve ..
 I hope its clear now .

  --
 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, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>>
>>> --
>>> Regards,*
>>> Aanchal Goyal*.
>>>
>>>
>>
>>
>> --
>> Regards,*
>> Aanchal Goyal*.
>>
>>
>
>
> --
> Regards,*
> Aanchal Goyal*.
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

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 wrote:

> @ 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 
> wrote:
>
>> 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 achieving the sum*/
>>
>>
>> So, ho here n=5, but see how many times the solve function is called! if
>> it was n^2, then it would have been called just 25 times
>>
>> On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal wrote:
>>
>>> @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];i>>  {
>>>   index[n+1]=i;
>>>   solve(index,arr,target,cursum+arr[i],n+1,sz);
>>>  }
>>>
>>> Here sz is the number of elements in the array i.e. n for complexity.
>>> There is a recursive call to solve ..
>>> I hope its clear now .
>>>
>>>  --
>>> 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, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Regards,*
>> Aanchal Goyal*.
>>
>>
>
>
> --
> Regards,*
> Aanchal Goyal*.
>
>


-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

@ 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 wrote:

> 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 achieving the sum*/
>
>
> So, ho here n=5, but see how many times the solve function is called! if it
> was n^2, then it would have been called just 25 times
>
> On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal wrote:
>
>> @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];i>  {
>>   index[n+1]=i;
>>   solve(index,arr,target,cursum+arr[i],n+1,sz);
>>  }
>>
>> Here sz is the number of elements in the array i.e. n for complexity.
>> There is a recursive call to solve ..
>> I hope its clear now .
>>
>>  --
>> 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, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards,*
> Aanchal Goyal*.
>
>


-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

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 achieving the sum*/


So, ho here n=5, but see how many times the solve function is called! if it
was n^2, then it would have been called just 25 times

On Wed, Aug 3, 2011 at 9:55 AM, ankit sambyal wrote:

> @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];i  {
>   index[n+1]=i;
>   solve(index,arr,target,cursum+arr[i],n+1,sz);
>  }
>
> Here sz is the number of elements in the array i.e. n for complexity. There
> is a recursive call to solve ..
> I hope its clear now .
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[ankit sambyal]

@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];ihttp://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[Ravinder Kumar]

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 from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

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,
using the standard knapsack problem, we can't do this right?

On Wed, Aug 3, 2011 at 2:05 AM, Ravinder Kumar  wrote:

> 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 Allahabad
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[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 Allahabad

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

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 wrote:

> Can we prove this??
>
>
> On Wed, Aug 3, 2011 at 1:45 AM, Ravinder Kumar 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 Allahabad
>>
>>  --
>> 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, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards,*
> Aanchal Goyal*.
>
>


-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

Can we prove this??

On Wed, Aug 3, 2011 at 1:45 AM, Ravinder Kumar  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 Allahabad
>
>  --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[Ravinder Kumar]

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.
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[aanchal goyal]

really sorry for that,
here is the complete code:

#include

using namespace std;

void print(int arr[], int index[], int n)
{
 int i=1;
 while(i<=n)
  {
   cout void solve(int index[], int arr[], int target, int cursum, int n, int sz)
>
>  solve(arr,100,len);
>
> conflict between call and definition of function solve
>
> --
> *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.
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,*
Aanchal Goyal*.

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help..

[Ravinder Kumar]

void solve(int index[], int arr[], int target, int cursum, int n, int sz)

 solve(arr,100,len);

conflict between call and definition of function solve

-- 
*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.
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] complexity

[Puneet Gautam]

k...thanks...


On 7/28/11, Rajeev Kumar  wrote:
> @Puneet,
>  get_power(int a, int b) works in O(logb) as you keep on dividing b with
> 2...
> you are calling that method *P *times in *func(int p) *method.
> So it is *plogb...*u r passing 5 as b valueit will be *plog5*
>
> On Thu, Jul 28, 2011 at 11:45 AM, Puneet Gautam
> wrote:
>
>> @sachin: Explain pls...!!?
>>
>>
>> On 7/28/11, sachin sharma  wrote:
>> > it is O(plg5)
>> >
>> >
>> > Best Wishes
>> > Sachin Sharma
>> >
>> > --
>> > 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, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>> --
>> 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, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Thank You
> Rajeev Kumar
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] complexity

[Rajeev Kumar]

@Puneet,
 get_power(int a, int b) works in O(logb) as you keep on dividing b with
2...
you are calling that method *P *times in *func(int p) *method.
So it is *plogb...*u r passing 5 as b valueit will be *plog5*

On Thu, Jul 28, 2011 at 11:45 AM, Puneet Gautam wrote:

> @sachin: Explain pls...!!?
>
>
> On 7/28/11, sachin sharma  wrote:
> > it is O(plg5)
> >
> >
> > Best Wishes
> > Sachin Sharma
> >
> > --
> > 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, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Thank You
Rajeev Kumar

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] complexity

[Puneet Gautam]

@sachin: Explain pls...!!?


On 7/28/11, sachin sharma  wrote:
> it is O(plg5)
>
>
> Best Wishes
> Sachin Sharma
>
> --
> 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, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] complexity

[sachin sharma]

it is O(plg5)


Best Wishes
Sachin Sharma

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help ??

[Preetam Purbia]

T(n) = T(n-1) + T(n-2) + O(1)


On Sat, Jan 22, 2011 at 11:28 PM, Decipher  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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Preetam Purbia
http://twitter.com/preetam_purbia

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help ??

[Decipher]

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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity Help ??

[abhijith reddy]

O(2^n)

On Sat, Jan 22, 2011 at 8:58 PM, Decipher  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 to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity of Algorithms

[sharad kumar]

use master theorem or recursion tree method

On Wed, May 5, 2010 at 7:29 PM, Varun Nagpal wrote:

> Complexity of an algorithms is focussed on two aspects: Time it takes to
> execute the algorithm(Time Complexity) and the amount of space in memory it
> takes to store the associated data(Space Complexity). Most literature in
> computer science focuses on Time Complexity as it directly influences the
> performance of algorithm.
>
> The complexity of an algorithm is usually based on a model of machine on
> which it  will execute. The most popular model is 
> RAMor Random Access 
> Machine Model. Simple assumption of this machine model is
> that every operation(arithmetic and logic) takes unit or single step and
> each of this step takes some constant time. So by finding the number of
> steps it takes to execute the algorithm, you can find the total time it
> takes to execute the algorithm.  In this sense Unit Time or Unit Step are
> considered equivalent or synonymous. Although RAM is not accurate model of
> actual machine, but its main advantage is that it allows a machine
> independent analysis & comparison of algorithms.
>
> So, the Time Complexity of an algorithm is measured in terms of the total
> number of steps the algorithm takes before it terminates. It is expressed
> usually as a function of Input Size or problem size. Input size can have
> different meanings, but for simplicity you can assume it to be number of
> objects that is given as input to the algorithm(say N). An object could mean
> an integer, character etc.  Now if T(N) is the time complexity of the
> algorithm
>
> T(N) = Number of steps(or time) it takes to execute the algorithm.
>
> T(N) could be a any mathematical function like a function in constant ,
> linear multiple of N function , polynomial in N function, poly-logarithmic
>  function in N, or Exponential function in N etc.
>
> Finding the Time Complexity of an algorithm basically involves analysis
> from three perspectives: worst case execution time, average case execution
> time and best case execution time. The algorithm will take different number
> of steps for different class of inputs or different instances of input. For
> some class of inputs, it will take least time(best case). For another class
> of inputs it will take some maximum time(worst case).
>
> Average case execution time analysis requires finding average(finding
> expectation in statistical terms) of the number of execution steps for each
> and every possible class of inputs.
>
> Best case execution time is seldom of any importance. Average case
> execution time is sometimes important but most important is Worst Case
> execution time as it tells you the upper bound on the execution time and so
> tells you lower bounds on obtainable performance.
>
> In Computer science though, expressing T(N) as a pure mathematical
> function is seldom given importance. More important is knowing asymptotic
> behavior of algorithm or asymptotic growth rate i.e how quickly does T(N)
> grows as N goes to a extremely large values(approaching infinity or exhibits
> asymptotic behavior).
>
> So instead of expressing T(N) as a pure and precise mathematical
> function, different other notations have been devised.
> As far as I know, there are at least 5 notations used to express T(N)
> namely Big-O ("O"), Small-o("o"), Big-Omega("Ω"), Small-omega("w"),
> Theta("*Θ"). *
>
> Big-O is used for representing upper bound(worst case), while Big-Omega is
> for expressing lower bounds(best case). Small or Little notations are more
> stricter notations. Theta notation is used for expressing those functions
> whose upper and lower bounds are  same or constant multiple of the same
> function
>
> For more thorough understanding, I suggest you to read the following: How
> to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23,
> 24, 25, 26, 27
>
> Regards
> Varun
>
>
>
>
>
>
> On Mon, May 3, 2010 at 8:15 PM, scanfile  wrote:
> > Pls can anyone help me out that how to calculate the complexity of any
> > Algorithm?
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> > For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
yezhu malai vaasa venkataramana Govinda Govinda

-- 
You received this message because you are subscribed to the Google Groups 
"Algor

Re: [algogeeks] Complexity of Algorithms

[Varun Nagpal]

Complexity of an algorithms is focussed on two aspects: Time it takes to
execute the algorithm(Time Complexity) and the amount of space in memory it
takes to store the associated data(Space Complexity). Most literature in
computer science focuses on Time Complexity as it directly influences the
performance of algorithm.

The complexity of an algorithm is usually based on a model of machine on
which it  will execute. The most popular model is
RAMor Random
Access Machine Model. Simple assumption of this machine model is
that every operation(arithmetic and logic) takes unit or single step and
each of this step takes some constant time. So by finding the number of
steps it takes to execute the algorithm, you can find the total time it
takes to execute the algorithm.  In this sense Unit Time or Unit Step are
considered equivalent or synonymous. Although RAM is not accurate model of
actual machine, but its main advantage is that it allows a machine
independent analysis & comparison of algorithms.

So, the Time Complexity of an algorithm is measured in terms of the total
number of steps the algorithm takes before it terminates. It is expressed
usually as a function of Input Size or problem size. Input size can have
different meanings, but for simplicity you can assume it to be number of
objects that is given as input to the algorithm(say N). An object could mean
an integer, character etc.  Now if T(N) is the time complexity of the
algorithm

T(N) = Number of steps(or time) it takes to execute the algorithm.

T(N) could be a any mathematical function like a function in constant ,
linear multiple of N function , polynomial in N function, poly-logarithmic
 function in N, or Exponential function in N etc.

Finding the Time Complexity of an algorithm basically involves analysis from
three perspectives: worst case execution time, average case execution
time and best case execution time. The algorithm will take different number
of steps for different class of inputs or different instances of input. For
some class of inputs, it will take least time(best case). For another class
of inputs it will take some maximum time(worst case).

Average case execution time analysis requires finding average(finding
expectation in statistical terms) of the number of execution steps for each
and every possible class of inputs.

Best case execution time is seldom of any importance. Average case execution
time is sometimes important but most important is Worst Case execution time
as it tells you the upper bound on the execution time and so tells you lower
bounds on obtainable performance.

In Computer science though, expressing T(N) as a pure mathematical
function is seldom given importance. More important is knowing asymptotic
behavior of algorithm or asymptotic growth rate i.e how quickly does T(N)
grows as N goes to a extremely large values(approaching infinity or exhibits
asymptotic behavior).

So instead of expressing T(N) as a pure and precise mathematical
function, different other notations have been devised.
As far as I know, there are at least 5 notations used to express T(N) namely
Big-O ("O"), Small-o("o"), Big-Omega("Ω"), Small-omega("w"), Theta("*Θ"). *

Big-O is used for representing upper bound(worst case), while Big-Omega is
for expressing lower bounds(best case). Small or Little notations are more
stricter notations. Theta notation is used for expressing those functions
whose upper and lower bounds are  same or constant multiple of the same
function

For more thorough understanding, I suggest you to read the following: How to
think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24,
25, 26, 27

Regards
Varun






On Mon, May 3, 2010 at 8:15 PM, scanfile  wrote:
> Pls can anyone help me out that how to calculate the complexity of any
> Algorithm?
>
> --
> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
> For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity of Algorithms

[Yalla Sridhar]

it is impossible 2 give a formula or a generic method to calculate the
complexity for any algo..

method to calcuate complexity differs per algo

On Mon, May 3, 2010 at 11:45 PM, scanfile  wrote:

> Pls can anyone help me out that how to calculate the complexity of any
> Algorithm?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Complexity of Algorithms

[rajesh kumar]

check  the design and analysis of algorithm by thomas cormen

On Mon, May 3, 2010 at 11:45 PM, scanfile  wrote:

> Pls can anyone help me out that how to calculate the complexity of any
> Algorithm?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.