Size: a a a

2020 April 08

A

Ajay in pro.algorithms
There are N<=10 people.
источник

A

Ajay in pro.algorithms
I'm trying brute force way of approaching the above problem and want to know the time complexity.
Like, for every t-shirt I'm trying to assign it a person(there can be many) and after assigning a person to this t-shirt, I'm recursing for next t-shirt and doing the same until I'm done with assigning all the people.
How can I evaluate the time-complexity from here?
источник

MB

Mikail Bagishov in pro.algorithms
I think it is O(answer)
источник

A

Ajay in pro.algorithms
Mikail Bagishov
I think it is O(answer)
what's "answer"?
источник

MB

Mikail Bagishov in pro.algorithms
Answer to the test
источник

MB

Mikail Bagishov in pro.algorithms
If your program printed 1000, it made approx. 1000 leaf recursion calls
источник

A

Ajay in pro.algorithms
Mikail Bagishov
If your program printed 1000, it made approx. 1000 leaf recursion calls
Is there a way to generalise the no. of recursive calls. For eg - Assuming that there are 10 people and each person has 1 to 100 t-shirt. How do we evaluate the time-complexity for this?
источник

MB

Mikail Bagishov in pro.algorithms
In worst case each person can wear all 100 shirts.
Complexity on such test will be
100 * (100 - 1) * (100 -2 ) * ... * (100 - N + 1) recursive calls
источник

MB

Mikail Bagishov in pro.algorithms
K := 100

we get (factorial(K) / factorial(K-N)) calls.
It should be multiplied by time spent in one call, e.g. O(K)
источник

A

Ajay in pro.algorithms
Mikail Bagishov
In worst case each person can wear all 100 shirts.
Complexity on such test will be
100 * (100 - 1) * (100 -2 ) * ... * (100 - N + 1) recursive calls
Isn't it something like no. of ways of distributing r things(t-shirts) to n people which is => C(n+r-1, r-1) ?
источник

A

Ajay in pro.algorithms
in the case where each person can wear all 100 t-shirts
источник

MB

Mikail Bagishov in pro.algorithms
Ajay
Isn't it something like no. of ways of distributing r things(t-shirts) to n people which is => C(n+r-1, r-1) ?
C(n+r-1, r-1) is another formula, it does not help in this problem.
E.g. consider N=101.
Answer is, obviously, 0.
But C(101+100-1, 100-1) is nonzero
источник

A

Ajay in pro.algorithms
Mikail Bagishov
C(n+r-1, r-1) is another formula, it does not help in this problem.
E.g. consider N=101.
Answer is, obviously, 0.
But C(101+100-1, 100-1) is nonzero
i think, it holds true for the case where r>N
источник

MB

Mikail Bagishov in pro.algorithms
Ajay
i think, it holds true for the case where r>N
well, N = 3, r = 5.
Answer is 5! / 2! = 120/2 = 60.
C(3+5-1, 5-1) = C(7, 4) = 35.
источник

MB

Mikail Bagishov in pro.algorithms
C(n+r-1, r-1) is number of ways to express R as sum of N non-negative numbers.
источник

A

Ajay in pro.algorithms
Mikail Bagishov
In worst case each person can wear all 100 shirts.
Complexity on such test will be
100 * (100 - 1) * (100 -2 ) * ... * (100 - N + 1) recursive calls
Yes, that's a way. Let's think  it the other way. Recursing over all t-shirts and for each t-shirt choosing only those people who have not been assigned a t-shirt till now. So, I start with the first t-shirt and iterate  over all the eligible people who can wear it. Then after assigning a t-shirt to one of the person, we recurse for the next t-shirt and assign the 2nd t-shirt to some eligible person(also this person shouldn't have been assigned a t-shirt in the previous recursions) and do this until all person are assigned a t-shirt. Also, for a t-shirt there can be no person who is assigned this t-shirt(because for eg- if we have 100 t-shirts and 10 people then there are 90 t-shirts which aren't worn by anyone).

How do I assess the time-complexity for goins this way?
источник

A(

Andrey (@AndrewB330) in pro.algorithms
Ajay
Yes, that's a way. Let's think  it the other way. Recursing over all t-shirts and for each t-shirt choosing only those people who have not been assigned a t-shirt till now. So, I start with the first t-shirt and iterate  over all the eligible people who can wear it. Then after assigning a t-shirt to one of the person, we recurse for the next t-shirt and assign the 2nd t-shirt to some eligible person(also this person shouldn't have been assigned a t-shirt in the previous recursions) and do this until all person are assigned a t-shirt. Also, for a t-shirt there can be no person who is assigned this t-shirt(because for eg- if we have 100 t-shirts and 10 people then there are 90 t-shirts which aren't worn by anyone).

How do I assess the time-complexity for goins this way?
it is still O(Answer)
источник

A

Ajay in pro.algorithms
Andrey (@AndrewB330)
it is still O(Answer)
Any lower bound?
источник

A(

Andrey (@AndrewB330) in pro.algorithms
Answer can be 0 - ~10^100, so it only depends on the answer how mush steps it will take (I think)
источник

A(

Andrey (@AndrewB330) in pro.algorithms
something like CollectionSize(1) * CollectionSize(2) * .... * CollectionSize(N)
источник