Complexity Problem

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • desaurido
    New Member
    • Nov 2009
    • 2

    Complexity Problem

    I have an algorithm wich I'm trying my best to find it's complexity but I realy have a problem with recursions. I have two versions.
    I've come down to this:
    Version1: T(n) = 2n * Sum(1<i<n)[ T(i) + T(n-i) ]
    Version2: T(n) = n * Sum(1<i<n)[ T(i) + T(n-i) ]

    I wanna know the complexity in the form of O(something), can anyone enlight me on this?
  • desaurido
    New Member
    • Nov 2009
    • 2

    #2
    Originally posted by desaurido
    I have an algorithm wich I'm trying my best to find it's complexity but I realy have a problem with recursions. I have two versions.
    I've come down to this:
    Version1: T(n) = 2n * Sum(1<i<n)[ T(i) + T(n-i) ]
    Version2: T(n) = n * Sum(1<i<n)[ T(i) + T(n-i) ]

    I wanna know the complexity in the form of O(something), can anyone enlight me on this?
    I forgot to say that T(0) = T(1) = 1

    Comment

    • JosAH
      Recognized Expert MVP
      • Mar 2007
      • 11453

      #3
      What is T(2)? It isn't defined by your recurrence relations (1 < i < n)

      kind regards,

      Jos

      Comment

      • shabinesh
        New Member
        • Jan 2007
        • 61

        #4
        Can you give insight of your algorithm. and might be helpful for better understanding.

        Comment

        Working...