Foundations of Algorithm Analysis

Question 1

Run Time

Answer 1

The running time of an algorithm varies with the input and typically grows with the input size

Question 2

following run times

Answer 2

❑Best case
❑Worst case
❑Average case

Question 3

The average case

Answer 3

*difficult to determine
❑Take all inputs and calculate time for all inputs
❑Sum all calculated values and divide by total input

Question 4

The best case

Answer 4

• not very informative
  ❑Might not happen very often

Question 5

worst case

Answer 5

❑Easier to analyse
❑Crucial to applications such as air traffic control, surgery, finance,…
❑E.g. Real time applications

Question 6

Limitations of Experimental Studies

Answer 6

❑It is sometimes difficult to implement the algorithm
❑Results may only be indicative of the running time for some inputs, but not for all possible inputs
❑One algorithm can perform better than the rest for some inputs. For other inputs,
another algorithm could be better
❑In order to compare two algorithms, the same hardware and software environments must be used
❑However, we will still measure the run time of some of our experiments for practice purposes…

Question 7

What is Asymptotic Analysis

Answer 7

❑The technique uses a high-level description of the algorithm instead of an implementation
❑We evaluate the performance of an algorithm in terms of input size. ❑We calculate how the time taken by an algorithm increases with the input size

Question 8

Estimating “Running Time”

Answer 8

❑Write down an algorithm
❑Using Pseudo-Code
❑In terms of a set of primitive operations
❑Count the number of steps
❑Consider worst-case input
❑Bound or “estimate” the running time
❑This leads to the Big-Oh (Big-O) notation for computational complexity

Question 9

what is T(n)

Answer 9

❑To measure the running time/computation of an algorithm
❑We refer to this resultant formulae as T(n)where nis the size of the input
❑If there is more than one input we might have T(n,m)(etc…) where nand mare the sizes of the inputs
❑We can use T(n)to compute the Big-O notation

Question 10

Pseudo-Code

Answer 10

❑Not an actual programming language…
❑Pseudo-Code is a cross between a programming language and written text
❑It is used to represent algorithms in a programming language-independent manner
❑We often specify the input and output and number the lines
❑The Pseudo-Code I will now describe is an adaptation of a standard…
❑Once you can read one type of Pseudo-Code it is easy to follow any variations

Question 11

Primitive Operations

Answer 11

❑Basic computations performed by an algorithm
❑Identifiable in Pseudo-Code
❑Examples:
❑Evaluating an expression (x>y?)
❑Assigning a value to a variable (x=0)
❑Indexing into an array (for A[0]or A[i]we might use the mathematical notation a0or ai)
❑Calling a method
❑Returning from a method