VBSpike
Mar 6th, 2001, 09:19 PM
Does anybody know a simple way to learn how to use the Big-Oh notation?????????
I have a homework due Thursday that involves determining the complexity of various algorithms. While some of them are pretty easy, I'm having difficulties with more complex ones. My book does a really bad job explaining the problem (basically it doesn't say anything about actual complexity computing), and I'm kinda stuck. If anyone here knows how to do this stuff please help!!!!!!!
Here are some examples from my homework if someone is interested (it's written in Java):
a) Compute the complexity (in terms of num) of the following method.
Assume that the methods readObject() and close() in ObjectInputStream
have constant complexity O(1).
static Phone[] readPhoneList(File fname, int num) throws IOException,
ClassNotFoundException {
ObjectInputStream listln =
new ObjectInputStream(new FileInputStream(fname));
Phone record;
Phone[] newList = new Phone[num + 1];
int i = 1;
while (i <= num) {
record = (Phone)listln.readObject();
newList[i] = record;
i++;
}
listln.close();
return newList;
}
b) Compute the complexity (in terms of noOfParticipants) of the following
method. Assume that the method simulateGame(t1, t2) has constant
complexity O(1).
public void simulateLeague() throws NotEnoughTeamsException {
if (participantIndex == noOfParticipants)
for (int i = 0; i < noOfParticipants; i++)
for (int j = i + 1; j < noOfParticipants; j++)
simulateGame(participatingTeams[i],
participatingTeams[j]);
else
throw new NotEnoughTeamsException("Not enough teams in league");
}
c) Compute the complexity (in terms of n) of the following method. Assume
that A is an array of length n, that the method sort(A, n) has complexity
O(nlogn), and that the methods Random() and nextInt() have constant
complexity O(1).
void (int[] A, int n) {
Random rd = new Random();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
A[i] = rd.nextInt();
sort(A, n);
}
}
d) Compute the complexity (in terms of n) of the following piece of code:
sum = 0;
if (Math.odd(n)) {
for (int i = 0; i < n; i++)
sum += 1;
}
else
sum += n;
e) In a sorted array we can perform binary search to find a desired element.
A binary search algorithm keeps track of an index interval [lo, hi] in the
array within which the desired element resides. In each step, the interval
is divided into two parts by computing the index mid = (lo + hi)/2. If the
element at the index mid equals the desired element, we have found it and
do not need to continue the search. If the desired element is smaller, we
know that it resides in the interval [lo, mid - 1], and if it is larger,
we know it is in the interval [mid + 1, hi].
Compute the complexity (in terms of noOfElems) of the method binarySearch.
Is binary search better than linear search (stepping through each element
in the array until we find the desired element)?
int binarySearch(int k) {
// searches for element k in the array v
// if k is found, output the index in v which contains k
// otherwise, return -1
int out = -1;
int lo = 0;
int hi = noOfElems - 1;
while (lo <= hi) {
mid = (lo + hi)/2;
if (k == v[mid]) {
out = mid;
break;
}
if (k < v[mid])
hi = mid - 1;
else
lo = mid + 1;
}
return out;
}
f) Compute the complexity (in terms of n) of the following piece of code.
Assume that the array A contains some permutation of the numbers 0 to
(n - 1), i.e., A contains all numbers from 0 to (n - 1), but in random
order.
sum3 = 0;
for (int i = 0; i < n; i++)
for (int j = 0; A[j] != i; j++)
sum3 += 1;
g) Compute the complexity (in terms of n) of the following method:
void complicatedOperation(int n) {
int x = 1;
int sum = 0;
while (x < n) {
sum += x;
x *= 5;
}
h) Compute the complexity (in terms of n) of the following piece of code:
for (int i = 0; i < 10; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < i; k++)
values[i][j] = k;
i) Compute the complexity (in terms of noOfElems) of the following method.
Hint: The sum of all elements b^i for which i ranges from 0 to k,
sum_(i = 0)^k (b^i) = (b^(k + 1) - 1)/(b - 1)
void reallyComplicatedOperation() {
int x = 1;
while (x < noOfElems) {
for (int i = 0; i < x; i++)
values[i][x] = 10;
x *= 2;
}
}
I have a homework due Thursday that involves determining the complexity of various algorithms. While some of them are pretty easy, I'm having difficulties with more complex ones. My book does a really bad job explaining the problem (basically it doesn't say anything about actual complexity computing), and I'm kinda stuck. If anyone here knows how to do this stuff please help!!!!!!!
Here are some examples from my homework if someone is interested (it's written in Java):
a) Compute the complexity (in terms of num) of the following method.
Assume that the methods readObject() and close() in ObjectInputStream
have constant complexity O(1).
static Phone[] readPhoneList(File fname, int num) throws IOException,
ClassNotFoundException {
ObjectInputStream listln =
new ObjectInputStream(new FileInputStream(fname));
Phone record;
Phone[] newList = new Phone[num + 1];
int i = 1;
while (i <= num) {
record = (Phone)listln.readObject();
newList[i] = record;
i++;
}
listln.close();
return newList;
}
b) Compute the complexity (in terms of noOfParticipants) of the following
method. Assume that the method simulateGame(t1, t2) has constant
complexity O(1).
public void simulateLeague() throws NotEnoughTeamsException {
if (participantIndex == noOfParticipants)
for (int i = 0; i < noOfParticipants; i++)
for (int j = i + 1; j < noOfParticipants; j++)
simulateGame(participatingTeams[i],
participatingTeams[j]);
else
throw new NotEnoughTeamsException("Not enough teams in league");
}
c) Compute the complexity (in terms of n) of the following method. Assume
that A is an array of length n, that the method sort(A, n) has complexity
O(nlogn), and that the methods Random() and nextInt() have constant
complexity O(1).
void (int[] A, int n) {
Random rd = new Random();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
A[i] = rd.nextInt();
sort(A, n);
}
}
d) Compute the complexity (in terms of n) of the following piece of code:
sum = 0;
if (Math.odd(n)) {
for (int i = 0; i < n; i++)
sum += 1;
}
else
sum += n;
e) In a sorted array we can perform binary search to find a desired element.
A binary search algorithm keeps track of an index interval [lo, hi] in the
array within which the desired element resides. In each step, the interval
is divided into two parts by computing the index mid = (lo + hi)/2. If the
element at the index mid equals the desired element, we have found it and
do not need to continue the search. If the desired element is smaller, we
know that it resides in the interval [lo, mid - 1], and if it is larger,
we know it is in the interval [mid + 1, hi].
Compute the complexity (in terms of noOfElems) of the method binarySearch.
Is binary search better than linear search (stepping through each element
in the array until we find the desired element)?
int binarySearch(int k) {
// searches for element k in the array v
// if k is found, output the index in v which contains k
// otherwise, return -1
int out = -1;
int lo = 0;
int hi = noOfElems - 1;
while (lo <= hi) {
mid = (lo + hi)/2;
if (k == v[mid]) {
out = mid;
break;
}
if (k < v[mid])
hi = mid - 1;
else
lo = mid + 1;
}
return out;
}
f) Compute the complexity (in terms of n) of the following piece of code.
Assume that the array A contains some permutation of the numbers 0 to
(n - 1), i.e., A contains all numbers from 0 to (n - 1), but in random
order.
sum3 = 0;
for (int i = 0; i < n; i++)
for (int j = 0; A[j] != i; j++)
sum3 += 1;
g) Compute the complexity (in terms of n) of the following method:
void complicatedOperation(int n) {
int x = 1;
int sum = 0;
while (x < n) {
sum += x;
x *= 5;
}
h) Compute the complexity (in terms of n) of the following piece of code:
for (int i = 0; i < 10; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < i; k++)
values[i][j] = k;
i) Compute the complexity (in terms of noOfElems) of the following method.
Hint: The sum of all elements b^i for which i ranges from 0 to k,
sum_(i = 0)^k (b^i) = (b^(k + 1) - 1)/(b - 1)
void reallyComplicatedOperation() {
int x = 1;
while (x < noOfElems) {
for (int i = 0; i < x; i++)
values[i][x] = 10;
x *= 2;
}
}