cs341a1/q3/q3.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}{I have completed this question with no outside sources.}


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


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

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Testing primality [10 marks]}

Analyze the time complexity of the following pseudocode in terms of $n$ 
using big-$O$ notation. 
For this analysis, each operation on integers (including multiplication and squaring) takes constant time.

\begin{algorithm}
\caption{{\sc IsPrime($n$)}}
$j \gets 2$\;
\While{$j^2 \le n$}{
  $k \gets 2$\;
  \While{$j * k \le n$}{
    \If{$j * k = n$}{
      \Return False\;
    }
    $k \gets k+1$\;
  }
  $j \gets j+1$\;
}
\Return True\;
\end{algorithm}

\begin{solution}
We shall analyze the algorithm in order, by scope blocks. First, we assign j the initial value of 2. This takes constant time. Then, we have a loop. This loop iterates on j, and if we reduce ${j^2} \leq n$ to $j \leq \sqrt{n}$, and notice that j increments one at a time, we can see this loop will iterate $\sqrt{n}$ times in the worst case.

As for what we are doing $\sqrt{n}$ times, we have another loop, from k=2 to j*k$\leq$n (by 1 each time) in the worst case. Since j is at least 2, in the worst case, this loop will iterate n/2 times. This loop performs an if check and multiplication, which are constant time operations, so the inner loop is O(n).

So, since we are looping $\sqrt{n}$ times, and in each of those loops entering another loop of O(n), our total worst-case runtime is O($n\sqrt{n}$).
\end{solution}


\end{document}