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 n0 > 1 such that f(n) < cg(n) for every integer n > n0.More specifically, if we choose c = 7 and n0 = 11, we see that
Ask for help with this question.
logpn = logqn / logqp
so when comparing bases 2 and 10, we have that
log2n = log10n / log102
and
log102
is a constant.
So, the distinction between
log2n
and
log10n
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 n0)
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 |
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 |
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.