Answer the question
In order to leave comments, you need to log in
Asymptotic Complexity. Java. Did I solve the test problem correctly?
Hello! I am doing a test task for training, who can help with the test? Everything about Asymptotic Complexity. Java language.
Determine the asymptotic complexity of the following algorithm:
int[] array = new int[n];
for (int i = 0; i <= array.length - 2; i += 2) {
array[i] = i;
}
Answer O( n/2 )
Using O-notation, indicate, separated by commas, the asymptotic complexity of the following algorithms: a) Key lookup in a hash table
b) Arbitrary index access in an array
c) Arbitrary index access in a singly linked list
d) Access by an arbitrary index in a doubly linked list
f) Quick sort (quick sort) g) Search in a balanced tree
Answer
e) Deletion at an arbitrary index in a singly linked list
a) O(1) b) O(1) c) O(N) d) O(N) e) O(1) f) O(n log(n)) g) O(log n)
Answer the question
In order to leave comments, you need to log in
You don't fully understand what asymptotic complexity is. "Answer O( n/2 )" is fundamentally wrong, because O implies any constant factor. Even if there was a cycle from 1 to n*100..billion..zeros..00, the complexity would still be O(n).
e) wrong. In order to remove an arbitrary element of a linked list, you must first find it.
f) false, q-sort without modification can degenerate to O(n^2). O(n log n) on average.
The rest is correct.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question