0

if f(n,k) + f(n,k-1) = c1 * f(n-1,k-1) + c2 * f(n-1,k-2) then
what should be c1 and c2 in terms of big O notation. Are they polynomial in k or constant?

I am not able to expand this recurrence properly.

learner
  • 1,952
  • 7
  • 33
  • 62
  • Is it a misprint that you have f(n,k) in both parts? – dvvrd Nov 08 '13 at 15:58
  • it was a miss print thanks for correction – learner Nov 08 '13 at 15:59
  • Your equation seems even more complex that fibonacci equation, so it is at least expponential. Take a look here: http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence – dvvrd Nov 08 '13 at 16:07
  • I do not want time complexity, I need to know what can be possible value for c1 and c2 – learner Nov 08 '13 at 16:09

0 Answers0