4.2: Some Algorithms
- Page ID
- 18514
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
An algorithm is, informally, an explicit set of rules to follow to solve a problem.
Exercise \(\PageIndex{1}\)
Suppose we have a finite list of integers. Describe a method we could use to always find the greatest one.
Below, we give an algorithm in pseudocode to do just this.
algorithm for determining the greatest integer in a finite list
- Input: list of integers, \(\{a_1,a_2,\ldots,a_n\}\)
- Let \(\max := a_1\)
- For \(i\) from \(2\) to \(n\)
- if \(\max<a_i\) then \(\max := a_i\)
- Return \(\max\)
Definition
The time complexity of an algorithm is the time required to run an algorithm. It is usually measured in terms of the number of operations used by an algorithm and expressed in big-O notation.
How many operations does the previous algorithm require?
Exercise \(\PageIndex{2}\)
Determine an algorithm (written in pseudocode) and the time complexity of that algorithm for:
- computing the dot product of two vectors
- computing the product of two square matrices
- sorting a list of integers (so that it is arranged from least to greatest).