Recurrence relation for the number of “references” to two mutually recursive function

I was going through the Dynamic Programming section of Introduction to Algorithms(2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the assembly line scheduling portion.


$ (1),(2),(3)$ are three relations as shown.

$ $ f_{1}[j] = \begin{cases} e_1+a_{1,1} &\quad\text{if } j=1\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if} j\geq2\ \end{cases}\tag 1$ $

Symmetrically,

$ $ f_{2}[j] = \begin{cases} e_2+a_{2,1} &\quad\text{if } j=1\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if} j\geq2\ \end{cases}\tag 2$ $

(where $ e_i,a_{i,j},t_{2,j-1}$ are constants for $ i=1,2$ and $ j=1,2,3,…,n$ )

$ $ f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$ $


The text tries to find the recurrence relation of the number of times $ f_i[j]$ ($ i=1,2$ and $ j=1,2,3,…,n$ ) is referenced if we write a mutual recursive code for $ f_1[j]$ and $ f_2[j]$ . Let $ r_i(j)$ denote the number of times $ f_i[j]$ is referenced.

They say that,

From $ (3)$ ,

$ $ r_1(n)=r_2(n)=1.\tag4$ $

From $ (1)$ and $ (2)$ ,

$ $ r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$ $


I could not quite understand how the relations of $ (4)$ and $ (5)$ are obtained from the three corresponding relations.

Thought I could make out intuitively that as there is only one place where $ f_1[n]$ and $ f_2[n]$ are called, which is in $ f^\star$ , so probably in $ (4)$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition, however I would prefer an alternative to mathematical induction as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then I shall appreciate mathematical induction as well provided the intuition is explained to me properly).

Importance of space constructability in time space relation in complexity

I am reading Arora-Barak’s Complexity book. In Chapter 4, they state and prove the following theorem.

enter image description here

Why $ S$ should be space constructible? Wouldn’t all three containments of theorem hold, even if $ S$ is not space constructible?

My other question is about Remark 4.3, the book claims that if $ S$ is space constructible then you can make an $ NSPACE(S(n))$ machine halt on every sequence of non-deterministic choices by keeping a counter till $ 2^{O(S(n))}$ . I am not sure how we can keep such a counter in $ S(n)$ space. The space constructability of $ S$ implies that we can compute $ S(n)$ in $ O(S(n))$ space, not $ 2^{O(S(n))}$ in $ O(S(n))$ space.

How to solve this recurrence relation using substitution method

Can anyone explain to me how to demonstrate that,

T (n, d) ≤ T (n − 1, d) + O(d) + d/n (O(dn) + T (n − 1, d − 1))

is solved by

T (n, d) ≤ bnd! (b is a constant)

using the substitution method?

I have done this but I don’t know if it is correct.

  • T (n-1, d) ≤ b(n-1)d!
  • O(d) ≤ bd
  • d/n (O(dn) + T (n − 1, d − 1)) ≤ d/n (bnd + b(n-1)d(n-1)!)

Modeling a three-way association with optional relation


Business rules

I have three tables (Parties, Categories and Products) which representing the following relationships:

  • A product is classified by zero-one-to-many categories
  • A category classifies zero-one-or-many products

Then, I have the party relationships:

  • A product is classified by one-to-one party
  • A party classifies one-to-many products

In other words, a product doesn’t have to be assigned a category.

Design proposal

I have based my design on the proposal found here, but it’s not entirely applicable since want to enforce party_id for both Products and Categories:

How to model a three-way association that involves Product, Category and Label?

Three-way association design proposal

Question

Is the usage of the three-way association table correct in my proposal to avoid the risk of having the application layer assigning a product to a category without enforcing the party_id?

Big O recurrence relation

int function(int n) {    int i;     if (n <= 0) {        return 0;    } else {        i = random(n - 1);        return function(i) + function(n - 1 - i);    } } 

Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range [0,n]. If the average processing time is T(n), what is the value of T(6)T(6)?

Assume that all instructions other than the random cost a negligible amount of time.

This question was on Brilliant and I was following along their solution

              T(n)=T(i)+T(n−1−i)+1               T(n)=T(0)+T(n−1)+1               T(n)=T(1)+T(n−2)+1                     ....               T(n)=T(n−2)+T(1)+1               T(n)=T(n−1)+T(0)+1         nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)        (n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2) 

Subtract 1 from 2

            nT(n)−(n−1)T(n−1)=2T(n−1)+1 

$ \frac{T(n)}{n+1}$ = $ \frac{T(n-1)}{n}$ + $ \frac{1}{n(n+1)}$ . They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$ \frac{T(n)}{n+1}$ = $ \frac{1}{(1)(2)}$ + $ \frac{1}{(2)(3)}$ + … + $ \frac{1}{n(n+1)}$ = $ \frac{n}{n+1}$ . I do not understand how they got to this equation from the previous. ​