java - Simple Algorithm complexity -
i have algorithm , need finding complexity of (tightest possible upper bound)
for(int = 0; < n/2; i++) for(int j = 0; j < n/4; j++) for(int k = 0; k < n; k++) x++;
my analysis if n not divided in each loop, o(n^3)
. complexity still holds true, since each "for loop" reduce each operation o(log n)
complexity since divides n every time loop executes, making smaller , smaller (smaller o(n)
@ least).
i answer between o(log n)
, o(n^3)
. me getting tightest possible bound?
start inner loop :
for(int k = 0; k < n; k++) x++;
is o(n).
now 1 layer above :
for(int j = 0; j < n/4; j++)
is o(n) because takes n/4 j reach n , know o(n/4) = o(n)
and outer loop o(n).so complexity o(n^3)
because have 3 nested loop each o(n) , non of them have effect on each other.
Comments
Post a Comment