\documentclass[10pt]{article}

\PassOptionsToPackage{numbers, sort&compress}{natbib}

%\usepackage{changepage}

\usepackage{amsmath, amssymb, amsthm}
\usepackage{algorithm}
\usepackage{mathtools}
%\usepackage{caption}
%\usepackage{subcaption}
\usepackage{float}
\usepackage{framed}
\usepackage[noend]{algpseudocode}
\usepackage{enumitem}
\usepackage{thmtools, thm-restate}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage[hidelinks]{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{xcolor}         % colors
\usepackage{wrapfig}
\usepackage{tabularx}
\usepackage{makecell}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{multirow}
\usepackage{fancyhdr}
\usepackage[capitalize,noabbrev]{cleveref}

\renewcommand{\O}{\mathcal{O}}

\pagestyle{fancy}
\lhead{COMSC 312}
\rhead{Spring 2026}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newenvironment{solution}{\begin{proof}[Solution]}{\end{proof}}

\title{Homework 3: Algorithm Analysis II}
\date{}

\begin{document}

\maketitle
\thispagestyle{fancy}

\noindent You may work in groups, but you must write solutions yourself. List your collaborators at the top of your submission. 
As the semester progresses, when you are asked to design an algorithm, you will need to provide: (a) either pseudocode or a precise English description of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

\vspace{1em}

\noindent \textbf{Instructions for submission:} Submit your homework as a single PDF file to the course Gradescope page. Either scan your \emph{legible} handwritten solutions or type them up in \LaTeX. 

\begin{problem}
  Suppose $T(n)$ is the worst case running time of an algorithm on an input of size $n$, and we know that $T(n)$ is $\O(n^3)$ and $\Omega(n^2)$. For each of the following statements, determine whether it must be true, must be false, or could be either true or false. Give a brief justification for each.
  \begin{enumerate}[label=(\alph*)]
    \item $T(n)$ is $\O(n^{2})$. 
    \item $T(n)$ is $\Theta(n^3)$.
    \item $T(n)$ is $\Omega(n)$.
    \item $T(n)$ is $\Theta(n^{1.5})$.
    \item $T(n)$ is $\O(n)$.
    \item $T(n)$ is $\Theta(n^2 \log n)$.
  \end{enumerate}
\end{problem}

% Use this environment for your solutions.
% \begin{solution}
%     This is a sample solution.
% \end{solution}

\newpage
\begin{problem}
    Consider the following algorithm where $f(A, i, j)$ is an unknown algorithm that takes an array $A$ and two indices $i$ and $j$ and returns a number. 
    \begin{algorithm}[H]
        \caption{Mystery Algorithm}
        \begin{algorithmic}[1]
            \State $n \gets |A|$
            \State $sum \gets 0$
            \For{$i = 1$ to $n$}
                \For{$j = 1$ to $n$}
                    \State $sum \gets sum + f(A, i, j)$
                \EndFor
            \EndFor
        \end{algorithmic}
    \end{algorithm} 

    \begin{enumerate}[label=(\alph*)]
        \item Without knowing anything about $f$, what can we say about the running time of the Mystery Algorithm in terms of $n$? Justify your answer.
        \item Suppose we know that $f$ runs in $\O(1)$ time. What is the running time of the Mystery Algorithm in this case? Justify your answer.
        \item Suppose we know that $f$ runs in $\O(n^2)$ time. What is the running time of the Mystery Algorithm in this case? Justify your answer.
        \item Suppose we know that $f$ runs in $\Omega(n^2)$ time. What is the running time of the Mystery Algorithm in this case? Justify your answer.
    \end{enumerate}
\end{problem}



\end{document}
