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.

what big-o of nested loop, number of iterations in inner loop determined current iteration of outer loop?


Comments

Popular posts from this blog

aws api gateway - SerializationException in posting new Records via Dynamodb Proxy Service in API -

asp.net - Problems sending emails from forum -