1
$\begingroup$

T(m,n) = T(m-1,n) + T(floor(m/2), n-1)

Base conditions
T(m,n) = 1 when n = 0
T(m,n) = 0 when m < n

Edited: Below is the code for which I want to know the time complexity in terms of m and n.

#Python3 program to count total number of  
#special sequences of length n where  
#Recursive function to find the number of 
# special sequences 
def getTotalNumberOfSequences(m,n): 

    #A special sequence cannot exist if length  
    #n is more than the maximum value m.  
    if m<n: 
        return 0

    #If n is 0, found an empty special sequence  
    if n==0: 
        return 1

    #There can be two possibilities : (1) Reduce 
    #last element value (2) Consider last element  
    #as m and reduce number of terms  
    res=(getTotalNumberOfSequences(m-1,n)+
         getTotalNumberOfSequences(m//2,n-1)) 
    return res 

#Driver Code 
if __name__=='__main__': 
    m=10
    n=4
    print('Total number

of possible sequences:',getTotalNumberOfSequences(m,n))

$\endgroup$
  • 1
    $\begingroup$ Please edit the question to add a reference to the original problem. $\endgroup$ – Apass.Jack Jun 18 at 18:50
  • 1
    $\begingroup$ As a first step to solve the recurrence equation, please edit the question to list the first values of $T(m,n)$. For example, all $T(m,n)$ for $m, n\le 6$. $\endgroup$ – Apass.Jack Jun 18 at 18:52
  • 1
    $\begingroup$ How do you interpret $m/2$ when $m$ is odd? $\endgroup$ – Yuval Filmus Jun 18 at 21:09
  • $\begingroup$ @YuvalFilmus we take floor of m/2 when m is odd. $\endgroup$ – Prarthit Mehra Jun 19 at 4:36
  • 1
    $\begingroup$ It looks like it is not easy to find a tight bound for its time-complexity. $\endgroup$ – Apass.Jack Jun 19 at 17:34

Your Answer

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

Browse other questions tagged or ask your own question.