galagatron

Actually, the for loop for(int i=0.i<n;i++) {...} has complexity [TEX]\Theta(n)[/TEX]. It is true that it has complexity [TEX]O(n)[/TEX], but also that it has complexity [TEX]\Omega(n)[/TEX], and therefore by definition, it has complexity [TEX]\Theta(n)[/TEX]. As for the program containing the sequence of for loops for(int i=0.i<n;i++) {...} for(int i=0.i<n;i++) {...} The …

Here's how the code works: It produced two streams of numbers, the i's and the s's (where N is the length of each stream). i_n = (0,1,2,3,4,5,...,N-1) s_n=(0,1,4,11,18,29,...,s_{N-2} + 2(N-3) + 1) So, for example, an invariant would be that s is always equal to the sum of twice the …

Since your recursion doesn't create a recursion tree (there's always only 1 subproblem, and it's the same size as every other subproblem), and since the program recurses n-1 times, a simple recurrent equation, i.e., running time description, would be: T(n)= BIG_THETA(n-1) Assuming that by "(n * Fact(n-1)!" you meant "(n …