Midterm Flashcards
What is the definition of Euer’s constant?
- N2/3
- The error calculated during a summation series.
- 0.57721566
- The sum of all the errors for a Taylor Series
0.57721566
What is proof by Induction?
- A recursive definition that shows the trivial case is true.
- Showing that that something is true for a certain number k, and then showing it is true for k+1.
- That the alternative is false.
- A proof that states that it must be true if no one can find where it is false.
Showing that that something is true for a certain number k, and then showing it is true for k+1.
What is the definition of a recursive function or routine?
A function that calls itself.
A function that cannot call itself.
A function that can be used inside of another function.
A function that returns no values.
A function that calls itself
What is the difference between a class and an object?
A class is a definition while an object is the actual data. The object is the definition and the class is the actual data. There is no difference...they are the same thing. The class is the actual programming source code while the object is the executable.
A class is a definition while an object is the actual data.
Complexity Analysis measures _______ and _____
time and memory
____________ counts the number of operation that we expect to take the most time.
Operation Count
_____________ analysis describe the rate at which execution time increases in relation to the input size.
Asymptotic
The main focus of algorithmic analysis is the relationship between __________ and __________.
Running Time
Input Size
What are the two methods of analyzing algorithms?
Experimental Analysis
Theoretical Analysis
A type of analysis that requires algorithms to be coded and run to determine the results.
Experimental Analysis
f(n) = c
The constant function
Give three examples of operations defined by the constant function.
arithmentic Calculation, comparison operation, variable declaration, assignment statement, invoking a method or function.
Give an example of an algorithm that can be described using the logarithmic function?
binary search
Logorithmic functions grow __________ as the value of n grows?
Slower
The Linear function states that f(n) =
n
The size of the size of a linear function doubles when the input __________.
doubles
The NlogN function is grows ________ than the linear function.
faster
Give an example of an N-Log-N function.
merge sort
A Quadratic function grows _________ than an N-Log-N function?
faster
A nested loop represents what type of function?
Quadratic Function
A bubble sort is what type of function?
Quadratic Function
This notation represents the ___________ function
O(1).
Constant
Assume that algorithm 1 takes
time t1(n) = 100n+n2
and algorithm 2 takes
time t2(n) = 10n2
If the function has 10 inputs which algorithm is faster?
t2
Assume that algorithm 1 takes
time t1(n) = 100n+n2
and algorithm 2 takes
time t2(n) = 10n2
If the algorithm has 1000 inputs which is faster?
t1
Assume algorithms with the following times
Algorithm 1: insert - n, delete - log n, lookup - 1
Algorithm 2: insert - log n, delete - n, lookup - log n
Which algorithm is faster for an application with many lookups and few inserts?
Algorithm 1
What is the primary function of Asymptotic Complexity Analysis?
It compares the growth rate of two functions.
What are two factors that are eliminated when performing Asymptotic Complexity?
constant multipliers (co-efficient) lower-order effects
What type of notation if described here
T(N) <= cf(N)
BIG O
What type of notation if described here
T(N) >= cf(N)
Omega
What type of notation if described here
T(N) = cf(N)
Theta
What type of notation if described here
T(N) < cf(N)
Little O
f(N) = N logN and g(N) = N^1.5
Which one grows faster??
g(N)
Name the 4 steps in Complexity Analysis
Find the size of input n = size of the input Find atomic operations define f(n) as the number of atomic activities done by an input size of n. define the complexity of the algorithm as the complexity of f(n)
What is the complexity of the following?
for (int i = 0; i < n; ++i){
//operation
if( condition) break;
}
O(n)
if(condition) i = 0; else for ( j = 0; j < n; j++) a[j] = j;
O(N)
