java - Which one is faster?(from CTCI book) -


i came across 2 code snippets in ctci book,

code snippet 1:

int min = integer.max_value; int max = integer.min_value;   for(int x : array) {      if (x < min) min = x;     if (x > max) max = x; } 

code snippet 2:

int min = integer.max_value; int max = integer.min_value;   for(int x : array) {      if (x < min) min = x; }  for(int x : array) {     if (x > max) max = x; } 

the book didnt gave clear cut answer on 1 faster , more efficient assembly level , compiler optimization perspective. believe both of have o(n) running time. first 1 has 1 loop expense of 2 conditional operations while second one, loops twice 1 conditional operation.

to technically precise second run time o(2n) , first 1 o(n) since omit constants, both described o(n). let huge size of n, constant matter? 1 result in more optimized assembly code compiler perspective?

edit: constants no matter large size of n, comparing 2 code snippets, 1 has constant of 2, , other 1 not, effect running time, if run both of them parallel on same size of n , same machine specs?

to technically precise second run time o(2n) , first 1 o(n) since omit constants, both described o(n).

i don't think right. as far number of comparisons concerned (and essence here), in first case, doing 2 comparisons per iteration, whereas in second case there 2 loops, there 1 comparison per iteration in each. so, these 2 equivalent, since o(2n) = o(n) + o(n).

of course, several correct comments reveal practical aspects of running such code in silico. real reason find big-oh complexity of algorithm idea of how computation behaves without regards computational (machine) power , in presence of arbitrarily large n, input size (that's why asymptotically).


Comments

Popular posts from this blog

javascript - Slick Slider width recalculation -

jsf - PrimeFaces Datatable - What is f:facet actually doing? -

angular2 services - Angular 2 RC 4 Http post not firing -