Multiplication by a constant:

$f(n)inO(g(n))=>f(n)inO(g(n)),c>0$

Addition:

$a(n)inO(f(n))$&$b(n)in(g(n))=>a(n)+b(n)in(f(n)+g(n))$

Multiplication:

$a(n)in(f(n))$&$b(n)in(g(n))Longrightarrowa(n)b(n)inO(f(n)g(n))$

Transitivity:

$a(n)inO(f(n))$&$f(n)inO(g(n))Longrightarrowa(n)inO(g(n))$

Polynomials:

$f(n)$ is a polynomial of degree

Exponential bound on polynomial:

$n^x$inO$(a^n)$ for any fixed $x>0,a>1$

E$.$g$.,n^{1000}$inO$(2^n)$

Log of power:

$log{n}^x$inO$(logn)$ for any fixed $x>0$

Because: $log{n}^x=xlogninO(logn)$

Power of log:

$lo{g}^{x}n=(logn{)}^x$inO$(n^y)$ for any fixed $x>0,y>0$

Let $f(n)=(n+3)(n^2+1)$

$($a$)$ Find $g(n)$ such that $f(n)$ is $O(g(n)).$

$($b$)$ What are $c$ and $n_0$ that shows your answer is correct?

If $f(n)=n^{1000}+3n^2$ and $g(n)=2^n,$ is $f(n)ino(g(n))?$ Why or why not?

Suppose $f(n)=(lo{g}^{6}n)(log{n}^3).$ Show that $f(n)$ is $O(nlogn).$

Suppose we have the following algorithm:

Algorithm Cartesian $(A,B,n)$

Input: A and $B,$ two $n-$element lists

Output: The Cartesian product of the two lists: $[[A[0],B[0]],[A[0],B[1]],$dots$]$

Let $C$ be an empty list

for i from $0$ to $n-1$ do

for $j$ from $0$ to $n-1$ do

Add $[A[i],B[j]]$ to the end of $C$

return $C$

End.

$($a$)$ What is the time complexity using the RAM m$$del $($i$.$e$.,$ directly counting operations$)?$ Make sure you explain your answer in terms of the operations you consider primitive.

$($b$)$ Is this algorithm's running time $O(n^3)?$ Wh$$ or why not?

$($c$)$ Is this algorithm's running time $(n^2)?$ Why or why not?

$($d$)$ Is this algorithm's running time $(n)?$ Why or why not?

Suppose that we add a loop between lines $??$ and $??$ of the algorithm in question $??$ that prints the list, one element at a time. Which of the answers you gave in question $??$ would be different now? Why?