Question 1 What is the time complexity of the following Java snippet of code in
ID: 3548005 • Letter: Q
Question
Question 1
What is the time complexity of the following Java snippet of code in terms of n:
for (int k = 1; k <= n; k++) {
for (int i = 1, j = 1; i <= n, j <= n; i++, j++) {
if (a[i, j] && a[j, k]) a[i, k] = true;
}
}
How about the time complexity of the following Java snippet of code?
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= n; k++) {
for (int j = 1; j <= n; j++) {
if (a[i, j] && a[j, k]) a[i, k] = true;
}
}
}
A
The time complexity of the first snippet of Java code is O(n2), whereas the time complexity of the second snippet of Java code is O(n2);
B
The time complexity of the first snippet of Java code is O(n2), whereas the time complexity of the second snippet of Java code is O(n3);
C
The time complexity of the first snippet of Java code is O(n3), whereas the time complexity of the second snippet of Java code is O(n2);
D
The time complexity of the first snippet of Java code is O(n3), whereas the time complexity of the second snippet of Java code is O(n3);
E
Both snippets of Java code will lead to infinite loops.
Question 2
What is the maximum height of a well-balanced binary search tree with n nodes?
A
O(1);
B
O(log n);
C
O(n);
D
O(2n);
E
None of the above.
Question 3
How much is the time complexity of retrieve the element using the index for a hash table of n elements?
A
O(1);
B
O(log n);
C
O(n);
D
O(n2);
E
O(n3).
Question 4
Let us consider the following data structure called Node given by:
class Node<E> {
E element;
Node next;
public Node(E o) {
element = o;
}
}
We also assume that the head of the list is given:
private Node<E> head;
What does the following snippet of Java code?
Node<E> previous = head;
for (int i = 1; i < index; i++) previous = previous.next;
Node<E> current = previous.next;
previous.next = current.next; size--;
return current.element;
A
Insert the element at position index in the list and return the element that was inserted in the list.
B
Insert the first element of the list and return the element that was inserted in the list.
C
Insert the last element of the list and return the element that was inserted in the list.
D
Remove the element at position index in the list and return the element that was removed from the list.
E
None of the above.
A
The time complexity of the first snippet of Java code is O(n2), whereas the time complexity of the second snippet of Java code is O(n2);
B
The time complexity of the first snippet of Java code is O(n2), whereas the time complexity of the second snippet of Java code is O(n3);
C
The time complexity of the first snippet of Java code is O(n3), whereas the time complexity of the second snippet of Java code is O(n2);
D
The time complexity of the first snippet of Java code is O(n3), whereas the time complexity of the second snippet of Java code is O(n3);
E
Both snippets of Java code will lead to infinite loops.
Explanation / Answer
The time complexity of the first snippet of Java code is O(n2), whereas the time complexity of the second snippet of Java code is O(n3);
O(log n);
O(1)
Insert the last element of the list and return the element that was inserted in the list.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.