O
O
Oleg Zhukov2016-11-28 16:54:10
Java
Oleg Zhukov, 2016-11-28 16:54:10

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

1 answer(s)
D
Denis Zagaevsky, 2016-11-28
@Agnes_Dei

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 question

Ask a Question

731 491 924 answers to any question