algorithm - Finding the complexity of given code -
i battling find complexity of given code. think struggling identifying correct complexity , how analyze complexity. code analyzed follows:
public void dothings(int[] arr, int start){ boolean found = false; int = start; while ((found != true) && (i<arr.length)){ i++; if (arr[i]==17){ found=true; } } } public void reorganize(int[] arr){ (int i=0; i<arr.length; i++){ dothings(arr, i); } }
the questions are:
1) best case complexity of reorganize method , inputs occur?
2) worst case complexity of reorganize method , inputs occur?
my answers are:
1) reorganize method there 2 possible best cases occur. first when array length 1, meaning loop in reorganize , dothings method run once. other possibility when ith item of array 17 meaning dothings loop not run on ith iteration. in both cases best case=Ο(n).
2) worst case when number 17 @ end of array , when number 17 not in array. mean array traversed n×n times meaning worst case Ο(n^2 ).
could please me answer questions correctly, if mine incorrect , if possible explain problem?
"best case" array empty, , search nothing.
the worst case @ every single element because never see 17. other cases in between.
if (arr[i]==17){
"hottest path" of code, meaning ran often.
it execute total of n*(n-1)/2
times (i think did math right) in worst case because when set found = true
, reorganize
method doesn't know that, doesn't end, , continues search though scanned entire array.
basically, flatten code without methods. have question.
Comments
Post a Comment