a) double dotProduct(double[] a, double[] b){ double sum = 0.0; for (int i = 0 ;

Question

a) double dotProduct(double[] a, double[] b){
double sum = 0.0;

for (int i = 0 ; i < a.length ; i++){
sum += (a[i] * b[i]);
}return sum;
}

b)boolean inFirstFive(char c, String s)
{
int limit = 5;
if (s.length() < 5) {
limit = s.length();
}

for (int i = 0 ; i < limit ; i++) {
if (s.charAt(i) == c) {
return true;
}
}

return false;
}

c)int countCommonNumbers(double[] array1, double[] array2)
{
int count = 0;

for (int i = 0 ; i < array1.length ; i++) {
for (int j = 0 ; j < array2.length ; j++) {
if (array1[i] == array2[j]) {
count++;
break;
}
}
}

return count;
}

d)int foo(String s)
{
char[] c = new char[s.length()];
for (int i = 0 ; i < s.length() ; i++)
{
c[i] = s.charAt(i);
}

int count = 0;
for (int j = 0 ; j < c.length ; j++)
{
for (int k = j ; k < c.length ; k++)
{
if (c[j] == c[k])
{
count++;
}
}
}

return count;
}

e)void sort(double[] array)
{
for (int i = array.length - 1 ; i > 0 ; i--) {
for (int j = 0 ; j < i ; j++) {
if (array[j] > array[j+1]) {
double temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}

f)boolean containSameNumbers(double[] array1, double[] array2)
{
if (array1.length != array2.length) {
return false;
}

selectionSort(array1); // assume normal selection sort implementation
selectionSort(array2);

for (int i = 0 ; i < array1.length ; i++) {
if (array1[i] != array2[i]) {
return false;
}
}

return true;
}

g)void sort(double[] array)
{
boolean ok = true;
for (int i = 0 ; i < array.length-1 ; i++)
{
if (array[i] > array[i+1])
{
ok = false;
}
}

if (ok)
{
return;
}

selectionSort(array); // assume normal selection sort implementation
}

---
a) I believe is O(n) with n = the length of a.
b) This one, I know the run time of the first if statement would be O(5), right? Because it's less than... but then I don't know for to explain if someone inputs a String that has a length of less than 5.
As for c-g, the nested loops really confuse me.

Explanation / Answer

a)

The loop iterates n times with n the length of a; O(n)

b)

The loop iterates at most 5 times; O(1)

c)

The outer loop iterates n times, with n the length of array1; the inner loop iterates m times, with m the length of array2. O(nm)

d)

The inner and outer loop (of the nested loop) each iterate n times, with n the length of s. The first loop doesn't factor in because it only iterates n times. O(n^2)

e)

The inner and outer loop each iterate n times, with n the length of array. O(n^2)

f)

selectionSort is O(n^2) and is executed 2 times, once for array1 and once for array2. The loop is n iterations. Therefore, the method is O(n^2).

g)

The method can call selectionSort, which is O(n^2) with n the length of array. The loop iterates n times, so the method as a whole it is O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.