I know that :
$T(n,k)=T(n−1,k−1)+T(n−1,k)$ is the Pascal triangle.
But what is this then:
$T(n,k)=T(n−1,k−1)+T(n,k-1)$
Is there any name for it? I am trying to learn about it's time complexity etc, but I can't find anything online.
3
-
2$\begingroup$ What is the time complexity of a recurrence? Time complexity is usually associated with algorithms: it describes the asymptotic rate of growth of their running time. $\endgroup$– Yuval FilmusCommented May 3, 2022 at 2:53
-
2$\begingroup$ You might find it useful to know about oeis.org $\endgroup$– D.W. ♦Commented May 3, 2022 at 3:23
-
2$\begingroup$ Let $T'(n,m):=T(m,n)$. Rewrite the second recurrence. $\endgroup$– user16034Commented May 3, 2022 at 12:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The second recurrence is ALSO Pascal's Triangle (interchange n and k).
