%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Welcome to Overleaf --- just edit your LaTeX on the left,
% and we'll compile it for you on the right. If you give
% someone the link to this page, they can edit at the same
% time. See the help menu above for more info. Enjoy!
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article} % Loads settings for the document layout
\usepackage{amsmath}
\usepackage{graphicx}
% Preambel

% The following settings are used for title generation and will show up in the
% main document where the \maketitle command is set.
\title{BBM204 Assignment I}
\date{25.03.2017}
\author{Sarp Cikis-21426792}

% Main document

\begin{document} % The document starts here

\maketitle % Creates the titlepage
\pagenumbering{gobble} % Turns off page numbering

\newpage % Starts a new page
\pagenumbering{arabic} % Turns on page numbering

\section{Part I: Running Time Analysis}


\subsection{Analysis algorithm and finding the tilde notation}

\begin{figure}[h!]
  \caption{Code and time analysis}
  \centering
  \includegraphics[width=\textwidth]{V269Ldw.png}
\end{figure}

\begin{equation*}
 	Total Cost = c1+c2*(log(n)+1)+c3+c4*(log(n)+1)*log(n)+c5*log(n)*log(n)+c6*log(n)*log(n)+c7*log(n)
\end{equation*}
The time required for this algorithm is proportional to $log(n)^2$.

\subsection{5 Algorithms}

\begin{figure}[h!]
  \caption{Algorithm time-table as microseconds}
  \centering
\includegraphics[width=\textwidth]{4AY5UHB.png}
\end{figure}

From the table we can see that the stooge sort algorithm is the slowest working one by a long mile. Followed by Shaker sort algorithm and the Radix sort algorithm respectively. Unsurprisingly Maximum sub-array algorithm and Finding the second largest element function are much faster working functions, since they don't have to sort the arrays just make operations on them. This makes it so they don't have to use their time moving elements in an array(or list) which is a very time consuming operation.

\newpage

\begin{figure}
  \caption{Table of time as microseconds without stooge sort algorithm}
  \centering
\includegraphics[width=\textwidth]{m1trdcs.png}
\end{figure}

I had to make two different graphs since stooge sort takes up so much more time than the other algorithms. To make any kind of sense from a graph i had to take stooge sort out of it.

\begin{figure}[h!]
  \caption{Table of time as microseconds with the stooge sort algorithm}
  \centering
\includegraphics[width=\textwidth]{3JvYnFm.png}
\end{figure}

As i said we can clearly see from this graph that stooge sort algorithm takes up extremely high resources and its time to run increases exponentially with the amount of randomly generated elements in an array.

\subsubsection{Big o notation of functions}
\begin{figure}[h!]
  \caption{Second highest function}
  \centering
\includegraphics[width=\textwidth]{zP5QOHN.png}
\end{figure}

The second highest function takes O(n) time to find the second highest element of a list.

\begin{figure}[h!]
  \caption{Stooge sort algorithm}
  \centering
\includegraphics[width=\textwidth]{TlGBOxE.png}
\end{figure}

Stooge sort algorithm takes $O(n^{log(3)/log(1.5)})$ time to which is roughly equal to $O(n^{2.7095)})$ which makes Stooge sort the slowest algorithm by a long shot.
\newpage
\begin{figure}[h!]
  \caption{Radix sort algorithm}
  \centering
\includegraphics[width=\textwidth]{mL7QlBz.png}
\end{figure}
Radix sort algorithm takes O(wn) time to sort for n keys which are integers of word size w which makes radix sort better than most compassion based sorting algorithms for sufficiently large size of lists.

\begin{figure}[h!]
  \caption{Cocktail shaker sort algorithm}
  \centering
\includegraphics[width=\textwidth]{7UVopLP.png}
\end{figure}
Cocktail shaker sort algorithm takes $O(n^2)$ time to run.

\subsection{Question}
\begin{figure}[h!]
  \caption{Question}
  \centering
\includegraphics[width=\textwidth]{url.png}
\end{figure}
For an input size of 220 it would take 1129259.31977 operations to execute the algorithm if our hardware can perform $10^6$ operations per second it would take 1.12925931977 seconds to complete the algorithm which is closest to 1 the answer is A.
\end{document} % The document ends here