1
$\begingroup$

The problem is: count all increasing subsequence of s.

def main():
    print(count([3,2,4,5,4]))

def count(s: list) -> int:
    n = len(s)
    counter = 0

    result = {}

    if n == 0:
        return 0

    for i in range(n):
        counter += recurse(s[i+1:], s[i], result)

    return counter

def recurse(s: list, x: int, result: dict) -> int:
    n = len(s)
    counter = 0

    if n in result:
        return result[n]

    if n == 0:
        return 1

    for i in range(n):
        if s[i] > x:
            counter += recurse(s[i+1:], s[i], result)

    result[n] = counter + 1

    return counter + 1

Can anyone help me what is the time complexity of this algorithm?
What I know is T(count()) is O(n) * T(recurse(n)). Correct me if I'm wrong, T(recurse(s1, ...)) will be O(1) if I already calculated recurse(s1, ...) and that will make T(count(s)) = O(n).

$\endgroup$
3
$\begingroup$

Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:

  1. The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique)
  2. The time it takes to process an item, assuming you know the results of every recursive call it would have done (or a bound on this number)

In your case:

  1. The memoization saves elements up to $n=len(s)$ (every element in the dictionary is smaller or equal to $n$ and therefore you will calculate at most $n$ values)
  2. Processing each element takes $O(n)$ time (in the recurse function, there is a for i in range(n):)

Therefore, for every new element you calculate (there are at most $n$ such values) you will spend $O(n)$ time, and thus the algorithm will take $n\cdot O(n)=O(n^2)$ in the worst case analysis.

Notice this is not an improvement from any naive algorithm that goes through every sublist - as by combinatorical counting there are ${n\choose2}={n!\over2!\cdot(n-2)!}={n\cdot(n-1)\over2}=O(n^2)$ different sublists

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.