I need to do a time complexity anaylsis(best case and worse case) for every func
ID: 3746608 • Letter: I
Question
I need to do a time complexity anaylsis(best case and worse case) for every function in MyArray. I have posted my code below.
package apps;
public class MyArray {
int[] nums;
int numElements=0;
public MyArray(){
nums = new int[100];
}
public MyArray(int size){
nums = new int[size];
}
public MyArray(int[] numbers){
nums = new int[numbers.length];
for(int i=0; i<numbers.length;i++)
nums[i] = numbers[i];
numElements = nums.length;
}
public void remove(int val) {
int index = linearSearch(val);
if (index >= 0) { // if val is found
for(int i=index;i<numElements-1;i++)
nums[i] = nums[i+1];
numElements--;
}
}
public void add(int val) {
if (numElements < nums.length)// if nums is not full
nums[numElements++] = val;
else { // nums is full
int[] new_nums = new int[nums.length+1];
for(int i=0;i<nums.length;i++)
new_nums[i] = nums[i];
new_nums[new_nums.length] = val;
nums = new_nums;
numElements++;
}
}
public int findMaxIdx() {
int maxIdx = 0;
for(int i=1; i<nums.length; i++)
if(nums[i] > nums[maxIdx]) // new challenger is greater
maxIdx = i;
return maxIdx;
}
public int binarySearch(int val) {
int start = 0;
int end = nums.length-1;
int midpoint;
while(start<=end) {
midpoint = (start + end)/2;
if (val > nums[midpoint])
start = midpoint + 1;
else if (val < nums[midpoint])
end = midpoint - 1;
else // val == nums[midpoint]
return midpoint;
}
return -1;
}
public int search(int val) {
return linearSearch(val);
}
private int linearSearch(int val){
// returns the index of the given value 'val'.
// if 'val' is not found, returns -1
for(int i=0;i<nums.length;i++)
if (nums[i] == val)
return i;
return -1;
}
private void generateNumbers() {
// nums[0]=0, nums[1]=2, nums[2]=4,...
for(int i=0; i<nums.length; i++)
nums[i] = 2*i;
}
}
Explanation / Answer
package apps;
public class MyArray {
int[] nums;
int numElements=0;
// Best and worst time complexity = O(1)
public MyArray(){
nums = new int[100];
}
// Best and worst time complexity = O(1)
public MyArray(int size){
nums = new int[size];
}
// Best and worst time complexity = O(n); n is the lenght of array numbers
public MyArray(int[] numbers){
nums = new int[numbers.length];
for(int i=0; i<numbers.length;i++)
nums[i] = numbers[i];
numElements = nums.length;
}
/* BEST CASE:
* In best case, time complexity of linearSearch(val) is O(1) when
* the value is present in index 0.
* And in this case, the while loop will run (n-1) times.
* Hence, total time complexity = O(n)
* WORST CASE:
* In worst case, time complexity of linearSearch(val) is O(n) when
* the value is present in index n-1.
* And in this case, the while loop will run 0 times.
* Hence, total time complexity = O(n)
*/
public void remove(int val) {
int index = linearSearch(val);
if (index >= 0) { // if val is found
for(int i=index;i<numElements-1;i++)
nums[i] = nums[i+1];
numElements--;
}
}
/* BEST CASE:
* If the array is not full, then it takes O(1) to insert the element.
* WORST CASE
* If the array is full, first it takes O(n) times to copy the array into the new array (new_nums) and then
* O(1) time to insert the element.
* Therefore, total time complexity = O(n)
*/
public void add(int val) {
if (numElements < nums.length)// if nums is not full
nums[numElements++] = val;
else { // nums is full
int[] new_nums = new int[nums.length+1];
for(int i=0;i<nums.length;i++)
new_nums[i] = nums[i];
new_nums[new_nums.length] = val;
nums = new_nums;
numElements++;
}
}
/* BEST CASE and WORST CASE:
* In both the cases, the for loop will run n-1 times.
* Therefore, total time complexity = O(n)
*/
public int findMaxIdx() {
int maxIdx = 0;
for(int i=1; i<nums.length; i++)
if(nums[i] > nums[maxIdx]) // new challenger is greater
maxIdx = i;
return maxIdx;
}
/* BEST CASE and WORST CASE:
* Total time complexity = O(log n)
*/
public int binarySearch(int val) {
int start = 0;
int end = nums.length-1;
int midpoint;
while(start<=end) {
midpoint = (start + end)/2;
if (val > nums[midpoint])
start = midpoint + 1;
else if (val < nums[midpoint])
end = midpoint - 1;
else // val == nums[midpoint]
return midpoint;
}
return -1;
}
/* BEST CASE and WORST CASE:
* Total time complexity = O(log n)
*/
public int search(int val) {
return linearSearch(val);
}
/* BEST CASE: element val is present at index 0
* Time complexity = O(1)
* WORST CASE: element val is present at index n-1
* Time complexity = O(n)
*/
private int linearSearch(int val){
// returns the index of the given value 'val'.
// if 'val' is not found, returns -1
for(int i=0;i<nums.length;i++)
if (nums[i] == val)
return i;
return -1;
}
/* BEST CASE and WORST CASE:
* Total time complexity = O(n)
*/
private void generateNumbers() {
// nums[0]=0, nums[1]=2, nums[2]=4,...
for(int i=0; i<nums.length; i++)
nums[i] = 2*i;
}
}
NOTE: Please find the time complexities commented above each method.