Examine your three-of-a-kind code from the previous question. In the text box below determine the time complexity of the code:

2. Randomly picks an integer between 1 and n. Save this in a variable pick1 3. Randomly picks an integer between 1 and n. Save this in a variable pick2 4. Randomly picks an integer between 1 and n. Save this in a variable pick3 5. Go to step 3 until pick1 is equal to pick2 AND pick1 is equal to pick3

Hint: To answer this question you have to think about "probabilities". What is the probability that a specific number between 1 and n is chosen at random? Run your program multiple times using n=5 and extrapolate a general f(n) from this example (more hint: if n=5 then the odds of picking some number is one in five so what are the odds of picking the same number twice?).

Answer the following questions:

1. [4 marks]: Determine a worst-case time complexity formula f(n) for the algorithm (highlighted in red above).

2. [2 marks]: Determine worst case run-time Big-O i.e: O(f(n))

3. [2 marks]: Determine best case run-time. i.e: Omega f(n)

4. [2 mark]: Estimate Theta f(n) . ( average run-time ).

Note: for full marks you must THOROUGHLY explain your reasoning for your answers for each question 1-4.

Grading (10) marks.

For full marks, your answer must include an explanation (your work). This can be in the form of a couple of equations, or a short derivation, or a brief verbal argument.

Part marks will be assessed for incomplete or incorrect answers.

For full marks, you must use f(n), O, omega, theta explanation to express your answer.

A submission consisting only of the final answer with no explanation will receive no more than 1 mark.