Whats the worst case time and space complexity of different algorithms to find combination i.e. nCr Which algorithm is the best known solution in terms of time/space complexity?
Asked
Active
Viewed 2,428 times
0
-
1Do you mean finding the actual combinations, or the number of combinations? – Anthony Aug 13 '15 at 04:33
-
Finding the number as well as actual combinations – Yogi Joshi Aug 13 '15 at 05:14
-
The time and space complexity of generating all combinations is: http://mathworld.wolfram.com/Combination.html. The time and space complexity of finding the **number** of combinations is `O(1)`. – beaker Aug 13 '15 at 15:30
1 Answers
-1
O(n!) is the time complexity to generate all combinations one by one.
To find how many combinations are there, we can use this formula:
nCr = n! / ( r! * (n-r)! )
As @beaker mentioned, this count can be calculated in O(1) time (i.e., constant time).
devsathish
- 2,339
- 2
- 20
- 16
-
2How can you find nCr in O(1)? because you need to find n! in O(1) in that case. – Naveen Attri Jun 12 '16 at 18:47
-
@Naveen this is a basic combinatorical rule... sees Beaker link in the comments – Aviv Jun 13 '16 at 04:07
-
1@Aviv What do you mean? Who can calculate N! in O(1)? It's O(N) by nature. – Emadpres Apr 28 '19 at 15:53
-
1