If asked to discuss the time complexity of your solution, what would you say?


  • 8
    G

    In order to express a correct asymptotic time complexity in Big-Oh notation for the average case for the Combination Sum problem, we would need to make arguments on how the average set of candidates looks like and how it relates to the target.

    Of course, this is not easy to do. If you have ever looked at analysis for sorting algorithms, you know that it is not easy (and the input for sorting algorithms is just a set of numbers, here we also have a target).

    However, if asked to discuss the time complexity, what would you do?

    Would you take a particular case and pretend that that is the average case, without providing any proof?

    If you are in front of two solutions for this problem, how would you decide which one has the lowest time complexity?


  • 0

    Are you talking about time complexity or about average-case time complexity? You're mixing them up and it's not clear what you're asking.


  • 0
    G

    Yes, I should have been clearer. I'm more curious about average-case complexity, but if worst-case is easier to discuss, then let it be worst-case complexity.


  • 0
    H

    I can't initially come up with Big-O answer,
    I will try to exemplify somehow.

    Let's consider the set [1, 2, 3] and target 1000. The main purpose is to show possible big gap.

    Question #1: How many 1s do you need to get 1000?
    Answer is 1000, i.e. target, i.e. k.

    Question #2: How many combinations of 1,2,3 could you get with no possible duplicates and without matter of order?
    Answer is C(3,1) + C(3,2) + C(3,3) = 3 + 3 + 1. Like [1,2,3, 12,13,23, 123]

    Question #3: Q2 + with duplicates but with small target
    C(3,1) * target/1 + C(3,2) * target/2 + C(3,3) * target/3

    Question #4: Q3 + large target
    target * (C(3,1) * target/1 + C(3,2) * target/2 + C(3,3) * target/3)

    So, complexity of combinations series by itself is O(2^n) and in our current case O(k * 2^n)
    And it can be made O(k) (target) times (not amortized with target/n)

    Final result should be like O(k * k * 2^n)) = O (k^2 * 2^n) or vice versa.

    However I am not 100% sure and waiting for other comments.


  • 0
    K

    I am trying to understand the complexity as well.

    This is what I was thinking:

    The largest number of elements in a combination sum would be [min, min, min ...], and to get the upper bound, we can say that for each element in the max length combination array, we can pick from any of the elements we are given.

    Therefore, the complexity should be: len(candidates)^ (target/min(candidates))

    Please let me know if there are any problems with my analysis.


  • 23

    before 0, I need to clarify that my analysis is based on JAVA backtracking implementation

    (0) If you can understand Chinese, please see https://github.com/Deadbeef-ECE/Interview/blob/master/Leetcode/BackTracking/039_Combination_Sum.java directly.

    (1) Let us see the difference between Combination Sum and Combination Sum II:
    The input of Combination Sum has no dups, but each element can be used for MORE than one time.
    The input of Combination Sum II has dups, but each element can be used ONCE.

    (2) Let us understand the time complexity of Combination Sum II at the beginning:
    O(k * 2 ^ n) is the time complexity of Combination Sum II:
    k is average length of each solution, and we need O(k) time to copy new linkedlist when we get one combination.

    Solution space:
    Since we use one element ONLY for one time, so, for the combinations with k elements, the number of different choices is C(n, k). And most of the time, this number is far smaller than k. But what is the worst case?
    int[] arr = {1,1,1,1,1,1,1,1,1}, target is 2, in this case, the number can actually reach C(n,k).

    Considering that the combinations may have different length, which range from 0 ~ n. So, there are at most
    C(n,0) + C(n,1) + C(n,2) + ... C(n,n) solutions. We know that C(n,0) + C(n,1) + C(n,2) + ... C(n,n) = 2^n. Then we got the time complexity of Combination Sum II which is O(k * 2 ^ n).

    (3) Then how we convert Combination Sum to Combination Sum II?
    For example, given int[] arr = {2, 3, 4, 5, 6} and target is 10 and each element can be used for MORE than once.
    Actually, it is same with the problem: given int[] arr = {2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6}, and target 10, each element can be used for ONLY one time, which is the same description of Combination Sum II.

    And you must find that for the new array, each element E, which is smaller than target, will expand to ceil(target/E). Assume the new array has length n', we can get the time complexity which is O(k * 2 ^ n') using the same analysis of Combination Sum II.

    (4) Welcome to correct me if I made mistakes and I am happy to see that:)


  • 0
    J

    @yuhangjiang Hi, your analysis is great! However, I think for Combination Sum II, each element E should be expanded to floor(target/E), as you would never use three 4's for a target of 10.


  • 0

    @joranson Hi, thanks for your comment. I think it depends on when you make a judgement for summing over the target(before next recursion of after going to next recursion).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.