cs341a1/q1/a1q1.tex

\documentclass[11pt]{article}
\usepackage{amsthm,amsmath,amsfonts,amssymb}
\usepackage[ruled,noline,noend]{algorithm2e}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}

%%% Update the following commands with your name, ID, and acknowledgments.
\newcommand{\YourName}{Tareef Dedhar}
\newcommand{\YourStudentID}{20621325}
\newcommand{\YourAck}{This question was completed only with the teachings from CS courses here at uWaterloo.}

\newenvironment{solution}{\paragraph{Solution.}}{}


\title{
\vspace{-0.8in} \normalsize
\begin{flushright} \YourName \\ \YourStudentID \end{flushright}
\rule{\textwidth}{.5pt}\\[0.4cm] \huge Assignment 1: Question 1 \\
\rule{\textwidth}{2pt}
\vspace{-1in}
}
\date{}

\begin{document}
\maketitle
\paragraph{Acknowledgments.} \YourAck


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Asymptotics}

Prove or disprove each of the following statements.

\begin{enumerate}[(a)]
\item For any constant $b > 0$, the function $f : n \mapsto 1 + b + b^2 + b^3 + \cdots + b^n$ satisfies
\[
f(n) = \begin{cases}
\Theta(b^n) & \mbox{if } b > 1 \\
\Theta(1) & \mbox{if } b \le 1.
\end{cases}
\]

\begin{solution}
Since f(n) is a geometric series, we can express it as $\sum_{i=1}^{n} {b^i}$ = $\frac{1 - {b^N}}{1 - b}$ = $\frac{{b^n} - 1}{b - 1}$
Using this:\\
When b=1: $\lim{n\to\infty}{\dfrac{\tfrac{{b^n} - 1}{b - 1}}{b^n}}$=$\frac{{b^n} - 1}{{b^{n+1}} - b}$, which, by :'Hopital's rule = $1 \div b$. Since $0 \lt 1 \div b \lt \infty$ , we have a \theta bound.
\end{solution}

\item For every pair of functions $f, g : \mathbb{Z}^+ \to \mathbb{R}^{\ge 1}$ that satisfy $f = \Theta(g)$, the functions $F : n \mapsto 2^{f(n)}$ and $G : n \mapsto 2^{g(n)}$ also satisfy $F = \Theta(G)$.

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}


\item For every pair of functions $f, g : \mathbb{Z}^+ \to \mathbb{R}^{\ge 1}$ that satisfy $f = o(g)$, the functions $F : n \mapsto 2^{f(n)}$ and $G : n \mapsto 2^{g(n)}$ also satisfy $F = o(G)$.

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}

\end{enumerate}


\end{document}