State the approximate worst-case running time for each of the following. Appropr
ID: 3601301 • Letter: S
Question
State the approximate worst-case running time for each of the following. Appropriate answers are of the form “constant time” or “[X] in [Y]”, where [X] might be “linear,” “quadratic,” or the like, and [Y] is the name of the variable or quantity in question. For example, a traversal of an array is linear in the length of the array; if the array is named a, it is linear in a.length.
1.
2.
3.
4. ArrayList(Collection<? extends E> c) (the copy constructor for ArrayList)
5. ArrayList.size
6. Arrays.binarySearch
Thank you.
Explanation / Answer
Answer 1. here array is reversing but for loop will execute arraylength/2 but in complexity terms it will be the O(n).
Answer 2. here abs function provide output in O(1) so for this code complexity will be O(1).
Answer 3. In this question both for loops will execute till the length of the loop so there is O(n2) complexity.
Answer 4. Here the time complexity will be size of Arraylist means O(n).
Answer 5. ArrayList.size has the complexity O(1) because when the value is inserted in the Arraylist it will increase the size at that time .
Answer 6. Arrays.binarySearch has the time complexity O(log n) because
To do a binary search (half the elements) until you found it. In a formula this would be this:
1 = N / 2x
multiply by 2x:
2x = N
now do the log2:
log2(2x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N
this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.