Question $1(30$ points$)$ Answer the following questions. All running times refer to the worst$-$case analysis.

$1)$ Abby came up with an algorithm for some problem that runs in time $\backslash$Theta $($n$2$ log $($ n $)),$ and Bill came up

with an algorithm for the same problem that runs in time o $($n$2$ log $($ n $)).$ Based on this information,

which one would you choose? Why?

$2)$ Abby tells you that a certain algorithm runs in time O $($ n $3+200$ n $),$ and Bill tells you that the same

algorithm runs in time $($ n$3).$ Can both Abby and Bill be correct? Why?

$3)$ Abby tells you that a certain algorithm runs in time $($ n$2+200$ n $),$ and Bill tells you that the same

algorithm runs in time $($ n$3).$ Assume that both statements are correct, which one is more

informative, i$.$e$.,$ gives you a better estimation of the running time? Why?