Why does this recursion method work? I have explored it for a day or two, and I cannot figure out why
Problem Statement: I have a tree with node values ( i , j ) where i , j < 1. The children of each node take on the values (i - 1, j), (i - 1, j - 1), and (i, j - 1) respectively. Now, i and j have ...
Given the following recurrence: T(n) = T(n-1) + n^2 How can I prove it to be O(n^3) with the substitution method? The O(n^3) guess derives from the fact that at every step of the recursion we pay ...
Here are given two functions that calculate the sum of elements in a list. The proof should be done using induction. The hypothesis is: sum(as) = sum1(as, 0) def sum( as : List [ Int ] ) : Int = as ...
I'm trying to develop code/pseudocode to build a list of all permutations given the following data. I'm developing in a java-like language for a web app. I don't have any java libraries for this ...