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

Popular posts from this blog

android - MPAndroidChart - How to add Annotations or images to the chart -

javascript - Add class to another page attribute using URL id - Jquery -

firefox - Where is 'webgl.osmesalib' parameter? -