c++ code time complexity of && operator -
i have following 2 codes:
int i=0; while(i<=1000000000 && i!=-1) { i++; }
i think run-time complexity 4 billion
in while condition 3 operations (i<=1000000000),(i!=-1) , &&
, and
int i=0; while(i!=-1) { if(i>=1000000000) break; i++; }
which think run-time complexity 3 billion, in while condition 1 operation (i<=1000000000)
in if 1 operation (i!=-1)
, when run 2 code have same running time why that?
i have change 2 codes little bit follow:
int n = 1000000000; int i=0; while(i<=n && i!=-1) { i++; } int n = 1000000000; int i=0; while(i!=-1) { if(i>=n) break; i++; }
this time 3rd code block run in 2.6s
, 4th 3.1s
, why happened? time complexity of 4 codes?
i use dev-c++ ide.
time complexity , actual running time 2 different things.
time complexity has meaning when talking variable input size. tells how algorithm scales larger inputs. if assume input n
(or 1000000000
in first 2 cases), examples have linear time complexity. means, roughly, if take n
2 times larger, running time doubled.
actual running time somehow depends on complexity, can't reliably calculate it. reasons are: compiler optimizations, cpu optimizations, os thread management , many others.
i think 'time complexity' mean number of primitive operations computer execute. there no difference between
while(i<=1000000000 && i!=-1)
and
while(i!=-1) { if(i>=1000000000) break;
because most likely operator &&
implemented not 'take first operand, take second operand, , perform operation on them', sequence of conditional jumps:
if not firstcondition goto falsebranch if not secondcondition goto falsebranch truebranch: ... here loop body falsebranch: ... here code after loop
and that's did hands in second example. however, stuff only makes sense specific compiler , optimization settings (in release build loop eliminated entirely descent compiler).
Comments
Post a Comment