# Probabilistic Algorithm Analysis

:::warning
Consider the following randomized algorithm.

CountLargeRolls(n)
    c <- 0
    for i <- 1 to n do
        for j <- 1 to 2i do
            r <- a uniformly random integer from {1, 2, 3, 4, 5, 6}
            if r >= 5 then
                c <- c + 1
    return c

Answer the following questions. Briefly justify each answer.

1. Give a Big-O bound for the worst-case running time of `CountLargeRolls(n)`.

2. Let $X$ be the value returned by the algorithm. Use indicator random variables to compute $\mathbb E[X]$.

3. (Bonus 1P) A student claims:

> Since each roll has probability $\frac{2}{6}$ of increasing $c$, and there are $N$ outer-loop iterations, the expected value is $n \cdot \frac{2}{6}$.

Explain what is wrong with this reasoning.

4. (Bonus 1P) How would your answer to part 2 change if the condition were changed from `r >= 5` to `r = 6`?

:::