java - Another time complexity issue -
i've done these problems, not looking straight answer. looking guidance on whether or not doing correctly , if not, possibly explanation on why incorrect. :)
so have these 2 problems. i've commented logic in why got answers. if please verify doing correctly?
public static integer findtripleb(int[] anarray) { //method variable: n if (anarray.length <= 2) { return false; } //time complexity: 1 // use insertion sort sort anarray (int = 1; < anarray.length; i++) {//tc 1+(n+1)+n // insert anarray[i] int j = i-1; //tc 1 int element=anarray[i]; //tc 1 while (j >= 0 && anarray[j] > element) {//tc log(n) anarray[j+1] = anarray[j]; //tc 1 j--; //tc 1 } anarray[j+1] = element; //tc 1 } //total tc: (2n+2)(1+1+log(n)(2)) = (2n+2)(2+2log(n)) = 4n+(2log(n))(2n)+4+4log(n) // check whether anarray contains 3 consecutive // elements of same value (int = 0; < anarray.length-2; i++) {//tc 1+n-1+n if (anarray[i] == anarray[i+2]) {//tc 1 return new integer(anarray[i]);//tc 1 } }//total tc: (2n)(2) = 4n return null;//tc 1 } //total time complexity: 5+8n+4nlog(n)+4log(n)
for best case time complexity, got o(1) because if array >= length 2, return. worst case, came o(n*log(n)).
for 1 more simpler problem,
boolean findtriplea(int[] anarray) { //method variable: n if (anarray.length <= 2) { return false;//tc 1 }//tc 1 (int i=0; < anarray.length; i++) {//tc 1+n+1+n // check if anarray[i] occurs @ least 3 times // counting how occurs in anarray int count = 0;//tc 1 (int j = 0; j < anarray.length; j++) {//tc 1+n+1+n if (anarray[i] == anarray[j]) { count++; }//tc 1 }//total tc: 2n+2 if (count >= 3) { return true; }//tc 1 }//total tc: (2n+2)(1+2n+2+1) = (2n+2)(2n+4) = 4n2+12n+8 return false;//tc 1 }//total time complexity: 4n2+12n+9
for best case, same first problem, o(1). worst case, o(n^2).
are these correct and, if not, why not? again, i'm not looking answer. i'm looking guidance professor doesn't seem want , rest of class confused.
a few points here first example:
complexity analysis of algorithms is not single case of algorithm (with array size of 2 example), rather about how long algorithm take in best/worst/average case arbitrarily-sized inputs (so array of given size). technically, analysis looking @ behavior n (the size of input) tends infinity. therefore, the if statements before loops not affect asymptotic best-case performance of algorithms.
insertion sort's worst case o(n^2). can kind of time if input array sorted in reverse order. conclusion first case wrong. don't have write lengthy description of why case, here's explanation why it's o(n^2) here:
it's not entirely clear, however, how longer inner while loop take if have twice array size. after all, doesn't go through entire array. in fact, on average, goes through half array, our diagram here illustrates, less, in sort, , more, later in sort, half of array on average. , doesn't go way down index 0. will, again on average, scan through half sorted set before finding right spot. so, it's reasonable estimate inner-while loop must iterate through ¼ of array each time through outer for-loop. sorted set must search averages half size of array, , on average must hunt through half sorted set before finding right spot.
but, if it's ¼ of array, still double if array size doubles -- ¼ of 1000 250, , ¼ of 2000 500, twice much. , when array size doubles, inner while loop takes twice long on average, , must performed twice many times outer loop. insertion sort takes 4 times long run when array size doubles. it's run time proportional n^2, , o(n^2).
for best-case, wrong too. if "just returns" still going go through number of comparisons proportional (really, equal) number of elements in array (even if it's 2 elements). the best-case o(n) comparisons, have check whether each element in right position, but o(1) swaps (in case it's sorted in right order , there's nothing swap anywhere).
also, in code, returning boolean in 1 place , integers in 2 other places of same method. doesn't make sense.
hopefully that's clear.
Comments
Post a Comment