Analysis of Algorithms

Question 1

A set of steps to accomplish a task

Answer 1

Algorithm

Question 2

2 things we want from a computer algorithm

Answer 2

Correctness
Efficient Resource Usage (CPU, Memory)

Question 3

The theoretical study of computer-program performance and resource usage.

Answer 3

Analysis of Algorithms

Question 4

An algorithm that gives a correct solution but takes a long time might
be of little to no value.

Answer 4

Time Complexity

Question 5

Algorithms can be analyzed base on ________ and _________ complexities

Answer 5

Time and Space

Question 6

_____________ is the primary measure of efficiency.

Answer 6

Time

Question 7

Factors that can affect runtime

Answer 7

speed of the computer
programming language
compiler/interpreter
other programs running

Question 8

2 Types of Run Time Analysis

Answer 8

Empirical and Theoretical Analysis

Question 9

Implement the algorithm, then run with a timer.

Answer 9

Empirical Analysis

Question 10

We determine how long the algorithm takes as a function of the
size of its input: T(n).

Answer 10

Theoretical Analysis

Question 11

We focus on how fast the function that
characterizes the running time _______ with the input size.

Answer 11

grows

Question 12

We focus on how fast the function that characterizes the running time grows with the input size.

Answer 12

Theoretical Analysis

Question 13

Upper Bound

Answer 13

O-notation (Big O)

Question 14

is used to describe the upper bound or the maximum possible running time of the algorithm.

Answer 14

The O- notation

Question 15

O(g(n)) is a set of functions f(n) such
that there exists positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

Question 16

the upper bound is a __________________

Answer 16

guarantee

Question 17

The running time of an algorithm on a particular input is the number of _______________ or _______ executed.

Answer 17

primitive operations or steps

Question 18

Running time of loops:

At most the running time of the statements inside the loop times the
number of _________.

Answer 18

iterations

Question 19

Running time for consecutive statements

Answer 19

Get the maximum

Question 20

Running time for conditional statements

Answer 20

The running time of the test + the running time of the two branches.

Question 21

is the minimum number of times a piece of code is executed.

Answer 21

best-case running time

Question 22

is the maximum number of times a piece of code is executed.

Answer 22

worst-case running time

Question 23

Linear Search Best and Worst Case Run time

Answer 23

Best: O(1) at index 0
Worst: O(n) at index n-1 or not in the list

Question 24

Binary Search Best and Worst Case Run time

Answer 24

Best: O(1) at middle
Worst: O(log n)

Question 25

An algorithm is O(log n) if it _____________________________________
(usually by 1⁄2).

Answer 25

cuts the problem size by a fraction