chapter 2 Flashcards
what dose Analysis of algorithms refers to
determining how “good” an algorithm is, usually in
terms of running time and storage.
for what is algorithm analysis
allows you to make quantitative judgments about the value of one algorithm over another
allows you to predict whether the software will meet any efficiency constraints that exist.
T or F:
running time and memory are bounded resources
What is running time
How long an algorithm needs to produce the output.
The running time of an algorithm typically grows with…..
input size
Three estimated running time
best,
average and
worst
how to analyze an algorithm
in onw of these two ways
1-expermintal study (real code, some typical input test,depends on HW/SW)
2-theoritcal study (all pssiable inputs, indepndent from HW/SW)
what is expiermental study in algorithm analysis steps
1 implement the algorithm with code
2 run program diffrent possible input
3 mark up running time with functions in code like clock
4 plot the result
Limitations on expiermental study in algorithm analysis
some traits of theortical analysis
1-Uses a high-level description of the algorithm instead
of an implementation.
.
2-Represents running time based on the number of
primitive operations or steps executed.
.
3-Characterizes running time as a function of the input
size, n.
what is primtave operations and give some example of it
**basic computations performed by an algorithm
**
Examples:
Evaluating an expression
Assigning a value to a variable
Indexing into an array
Calling a method
Returning from a method
Indexing into an array
Calling a method are examples of
Primitive operations
i=1
loop (i<=1000)
application code
i=i+1
end loop
f(n)=1000
i=1
loop (i<n)
application code
i=i x 2
end loop
f(n)= log2 n
i=1
loop (i<=n)
j=1
loop (j<=n)
application code
j= j +1
end loop
i=i + 1
end loop
f(n)= n2