algorithms analysis

Question 1

what does correctness mean in algorithm analysis

Answer 1

an algorithm outputs the expected correct value

Question 2

what is time efficiency

Answer 2

how fast and alorithm is excuted to get the result. the running time depends on the number of instructions to excute

Question 3

what is space (memory) efficency

Answer 3

how much memory does the algorithm need during excution

Question 4

what are the 3 things algorithm analysis look at

Answer 4

• correctness
• time efficency
• space ( memory) efficency

Question 5

what are some things that affect run time

Answer 5

• hardware
• software
• typically grows with the input size

Question 6

what are the analysis types

Answer 6

• worst case
• best case
• average case

Question 7

what are the limitations to runnign experiments for run time

Answer 7

• it is nessary to implement the algorithm which could be hard
• in order to compare two algorithms the same hardware and eviroments must be used
• results may not be indicative of the running time on other inputs not included in the experiment

Question 8

what is theoretical analysis

Answer 8

• uses pseudocode instead of implementation
• characterizes running time as a function of the input size n
• take into account all possible inputs
• allow us to evaluate the speed of an algorithm independent of teh hardware/software enviroment

Question 9

how do you determinte the theoritical analysis of running time

Answer 9

determine the number of primitive operations ( basic operations) as a function of the input size

Question 10

what is a primative operation

Answer 10

• basic computatiions performed by algorithm
• assume to take a constant execution time
• largely independent from the programming language

Question 11

what are some examples of primative operations

Answer 11

ex

• assigning value to a variable
• evaluating an arithmetic expression or boolean expression
• accessing a single element of an array by index
• calling a method
• returning from a method

Question 12

if wose case is (3n-1) and 2n is the best case what id the what is the worst case time of it

Answer 12

a(2n) <= T(n) <= (3n-1)

a- is fastest primative operation
b is slowest primative operation

Question 13

does changing in hardware/ssoftware enviroment affect the growth rate of running time?

Answer 13

• this affects T(n) by a constant factor

- does not alter the growth rate of T(n)

Question 14

why does growth rate matter

Answer 14

• can distinguish efficient vs inefficient algorthims
• many large scale instances can be solved more easily
• many real world problems have large sizes
• small diffreneces on small input sizes

Question 15

what does not affect growth rate?

Answer 15

• constant factord

- lower order terms

Question 16

What is asymptotic analysis

Answer 16

foucuses on the growth rate of the running time as a fucntion of the input size n
- how the running time increases with the input size in the limit as the input size increases without bound

notation

• big oh
• big omega
• big theta

Question 17

What is some notation asymptotic analysis

Answer 17

• big oh
• big omega
• big theta

Question 18

Big oh notation formula given f(n) and g(n)

Answer 18

we say f(n) is O(g(n) if there is a real positve constant c> 0 and interger constant n0 >= 1

so formula f(n) <= cg(n) for n>=n0

Question 19

big omega formula given f(n) and g(n)

Answer 19

we say f(n) is (g(n) if there is a real positve constant c> 0 and interger constant n0 >= 1

f(n) >= cg(n) for n>=n0

we say f(n) is O(g(n)) if both f(n) is O(g(n)) and f(n) is g(n)

Question 20

what does f(n) us O(g(n) do

Answer 20

• f(n) is of order AT MOST g(n). f(n) is NOT faster then g(n) asymptotically
• g(n) is an asymototic UPPER bound for f(n)

Question 21

f(n) is ( g(n))

Answer 21

• f(n) is of order at LEAST g(n). f(n) is NOT slower then g(n) asymptotically
• g(n) is an asymototic LOWER bound for f(n)

Question 22

f(n) is ( g(n))

Answer 22

• f(n) is of order g(n). f(n)

- g(n) is an asymptotic TIGHT bound for f(n)

Question 23

what is transpose symmetry

Answer 23

f(n) is O)g(n)) iff g(n) is f(n)

Question 24

symmetry

Answer 24

f(n) is O(g(n)) iff g(n) is f(n)

Question 25

transitivity

Answer 25

• f(n) is O)g(n)) and g(n) is O(h(n)) –> f(n) is O(h(n))
• f(n) is Og(n)) and g(n) is (h(n)) –> f(n) is O (h(n))
• • f(n) is Og(n)) and g(n) is O(h(n)) –> f(n) is O(h(n))

Question 26

whats the diffrence between polynomial run time and exponenetial run time?

Answer 26

• polynomial running time O(n^c) for some constant c>1
• preferably the constant factors are not very large

expontential running time O(2^n) some constant b>1
- should almost never be seen as efficent

Question 27

what are the big Oh properties

Answer 27

• drop the lower order term
• drop the constant factors

ex
x + 3x^2 + 2x +9 would be O(n^2)

Question 28

what are the general rules for loops, nested loops, concecutive statements, and if elseif-else statements

Answer 28

loops
the running time of the statements instide the nested loop times the number of iterations

• nested loops
  the running time of the statements insid ethe nested loops times the product of the sizes of all teh loops

-concecutive statements
add the running time

if - elseif -else statemenst
- the running time is the largest running times of the conditional blocks ( remember they are exclusive)

Question 29

how to get the runnning time of recursion calls

Answer 29

it depends on

• how many recursive activations occur
• for each invocation of the mehtod we only account for the number of operations that are performed within the body of activation
• take the sum over all activations