Algorithms and Analysis

Probability

Suppose there are A black balls and B white balls in a jar. We randomly pick a ball from the jar and put it back until we have a white ball. Denote X as the number of balls we have picked. What would be the distribution and expectation of X? (The distribution is the general formula for P(x = k) for each k N). (You should derive the expectation from the definition).

Substitution method T(n)=3T(2n)+O(n4) First use the master method to find the Upper bound(find O ), and then use the Substitution method to prove it is correct. T(n)={3T(2n)+O(n4)1n2n