Let f(n) and g(n) be functions mapping nonnegative integers to real numbers. We say that f(n) ... is of order g(n) ... if there is a real number c > 0 and a fixed integer n_{0} > 1 such that f(n) < cg(n) for every integer n > n_{0}.More specifically, if we choose c = 7 and n_{0} = 11, we see that
Ask for help with this question.
log_{p}n = log_{q}n / log_{q}p
so when comparing bases 2 and 10, we have that
log_{2}n = log_{10}n / log_{10}2
and
log_{10}2
is a constant.
So, the distinction between
log_{2}n
and
log_{10}n
is a constant,
and we can drop the constant out of
our big-O
by incorporating it into the value that we choose for c
(with an associated adjustment of n_{0})
in the above definition.
Ask for help with this question.
... An algorithm consists of a set of finite steps satisfying the following conditions:Input: two strings (which are of finite length by definition, since the abstract data type of a string has a length method)
1) Input: The number and type of input values must be made clear.
2) Precise specification of each step: Each step or instruction of an algorithm must be feasible and unambiguously defined.
3) Finiteness: for all input possibilities, the algorithm must terminate in finite time.
4) Result: It must be clear what the algorithm is intended to accomplish. There may be an output that spells out the outcome of the execution of the algorithm.
...
Ask for help with this question.
/ | n + 1, | if m = 0 | |
A(m,n) = | | | A(m-1,1), | if n = 0 |
\ | A(m-1,A(m,n-1)), | otherwise |
Demonstration:int A (int m, int n) { // A if (m == 0) return n + 1; if (n == 0) return A(m - 1, 1); return A(m - 1, A(m, n - 1)); } // A
% cat hw2q4a.cpp #include <iostream> int A (int m, int n) { // A if (m == 0) return n + 1; if (n == 0) return A(m - 1, 1); return A(m - 1, A(m, n - 1)); } // A int main () { // main int m, n; cout << "Enter m:" << endl; cin >> m; cout << "Enter n:" << endl; cin >> n; cout << "A(" << m << "," << n << ") = " << A(m, n) << endl; } // main % g++ hw2q4a.cpp % a.out Enter m: 3 Enter n: 2 A(3,2) = 29
/ | m, | if n = 0 | |
GCD(m,n) = | | | n, | if m mod n = 0 |
\ | GCD(n,m mod n), | otherwise |
Demonstration:int GCD (int m, int n) { // GCD if (n == 0) return m; if ((m % n) == 0) return n; return GCD(n, m % n); } // GCD
% cat hw2q4b.cpp #include <iostream> int GCD (int m, int n) { // GCD if (n == 0) return m; if ((m % n) == 0) return n; return GCD(n, m % n); } // GCD int main () { // main int m, n; cout << "Enter m:" << endl; cin >> m; cout << "Enter n:" << endl; cin >> n; cout << "GCD(" << m << "," << n << ") = " << GCD(m, n) << endl; } // main % g++ hw2q4b.cpp % a.out Enter m: 30 Enter n: 75 GCD(30,75) = 15
Ask for help with this question.
Answer:
Yikes!
Answer:
GCD(30,75) | | GCD(30,15)
Ask for help with this question.
ArrayClass
with the signature
ArrayClass (int arrayLength, int listLength, Object* list)
ArrayClass
with
arrayLength
elements,
such that:
arrayLength
>
listLength
,
then all of the elements of
list
are copied into the
first
listLength
elements of the
ArrayClass
instance;
arrayLength
elements of
list
are copied into the
ArrayClass
instance.
template <class Object> ArrayClass<Object>::ArrayClass ( int arrayLength, int listLength, Object* list) { // ArrayClass<Object>::ArrayClass int n; _size = 0; paObject = new Object[arrayLength]; if (paObject == NULL) throw ArrayMemoryException(); _size = arrayLength; if (arrayLength <= listLength) n = arrayLength; else n = listLength; for (int i = 0; i < n; i++) paObject[i] = list[i]; } // ArrayClass<Object>::ArrayClass
Ask for help with this question.
ArrayClass
and returns another instance of
ArrayClass
that has the same elements,
except that repeats of the same value are eliminated;
for example, applying the function to an array containing
4,12,64,12,92,12,53,92,4
will return an array containing
4,12,64,92,53.
(Hint: use a bucket array.)
Note: because this question may appear on an exam, a solution is not provided here.
References
^{1}
S. Radhakrishnan, L. Wise & C. N. Sekharan,
Object-Oriented Data Structures Featuring C++,
1999.
^{2}
S.L. Salas & E. Hille,
Calculus: One and Several Variables with Analytic Geometry,
3rd ed.,
John Wiley & Sons, New York, 1978,
p. 262.