I need to find time complexity analysis (best case and worse case) on all the fu
ID: 3746601 • Letter: I
Question
I need to find time complexity analysis (best case and worse case) on all the functions in MyArraySorted. I have attached my code for MyArraySorted below.
package apps;
public class MyArraySorted {
int[] nums;
int numElements=0;
public MyArraySorted(){
nums = new int[100];
}
public MyArraySorted(int size){
nums = new int[size];
}
public MyArraySorted(int[] numbers){
nums = new int[numbers.length];
for(int i=0; i<numbers.length;i++) {
insert(numbers[i]);
}
}
public void printArray() {
for(int i=0; i<numElements ; i++)
System.out.print(nums[i]+" ");
System.out.println();
}
public void remove(int val) {
int index = linearSearch(val);
if (index >= 0) {
int i = index;
while (i < (numElements -1)) {
nums[i] = nums[i - 1]; //shifts elements to right
i++;
}
// for(int i=index;i<numElements-1;i++)
// nums[i] = nums[i+1];
//nums[index] = nums[numElements-1];
numElements--;
}
}
public void add(int val) { //need to find the right place to add the given value and shift some numbers to the right to keep all numbers sorted
if (numElements < nums.length) { // if nums is not full
insert(val);
}
else { // nums is full
int[] new_nums = new int[nums.length*2];
for(int i=0;i<nums.length;i++)
new_nums[i] = nums[i];
new_nums[nums.length] = val;
nums = new_nums;
insert(val);
//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;
}
private 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 binarySearch(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;
}
private void insert(int number) {
int i=0;
if(numElements==0) {
nums[i]=number;
numElements++;
return;
}
while (i < numElements && nums[i] < number) {
i++;
}
int j = numElements - 1;
while (j >= i) {
nums[j + 1] = nums[j];
j--;
}
nums[i] = number;
numElements++;
}
}
Explanation / Answer
package apps;
public class MyArraySorted {
int[] nums;
int numElements=0;
// Best and worst time complexity = O(1)
public MyArraySorted(){
nums = new int[100];
}
// Best and worst time complexity = O(1)
public MyArraySorted(int size){
nums = new int[size];
}
// Best and worst time complexity = O(n); n is the lenght of array numbers
public MyArraySorted(int[] numbers){
nums = new int[numbers.length];
for(int i=0; i<numbers.length;i++) {
insert(numbers[i]);
}
}
// Best and worst time complexity = O(n); n is the lenght of array numbers
public void printArray() {
for(int i=0; i<numElements ; i++)
System.out.print(nums[i]+" ");
System.out.println();
}
/* 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) {
int i = index;
while (i < (numElements -1)) {
nums[i] = nums[i - 1]; //shifts elements to right
i++;
}
// for(int i=index;i<numElements-1;i++)
// nums[i] = nums[i+1];
//nums[index] = nums[numElements-1];
numElements--;
}
}
/* BEST CASE and WORST CASE:
* If the array is not full, then it takes O(1) to insert the element.
* If the array is full, then it takes O(n) times to copy the array and then
* O(n) time to insert the element.
* Therefore, total time complexity = O(n)
*/
public void add(int val) { //need to find the right place to add the given value and shift some numbers to the right to keep all numbers sorted
if (numElements < nums.length) { // if nums is not full
insert(val);
}
else { // nums is full
int[] new_nums = new int[nums.length*2];
for(int i=0;i<nums.length;i++)
new_nums[i] = nums[i];
new_nums[nums.length] = val;
nums = new_nums;
insert(val);
//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)
*/
private 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 binarySearch(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;
}
/* BEST CASE and WORST CASE:
* Total time complexity = O(n)
*/
private void insert(int number) {
int i=0;
if(numElements==0) {
nums[i]=number;
numElements++;
return;
}
while (i < numElements && nums[i] < number) {
i++;
}
int j = numElements - 1;
while (j >= i) {
nums[j + 1] = nums[j];
j--;
}
nums[i] = number;
numElements++;
}
}
NOTE: Please find the time complexities commented above each method.