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 1o(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
Post a Comment