math - The running time of my program in big O time -

can me figure out running time of loop? believe o(5nlogn).

for(int f = 0; f < array.length; f++) {     f = array[f];     for(int e = 0; e <= f; e++) {         e = array[e];         for(int d = 0; d <= e; d++) {             d = array[d];             for(int c = 0; c <= d; c++) {                 c = array[c];                 for(int b = 0; b <= c; b++) {                     b = array[b];                     for(int = 0; <= b; a++) {                         = array[a];                     }                 }             }         }     } } 

thanks

a way think space you're iterating over. if think it, loops iterate on nonnegative integral valuesof (a, b, c, d, e, f) where

n > f ≥ e ≥ d ≥ c ≥ b ≥ a

each of these iterations o(1) work (all loops assign variable, takes o(1) work), question how many possible values there satisfy above formula. i'm going claim it's θ(n⁶), , try justify rest of answer.

first, note value isn't more o(n⁶). of a, b, c, d, e, , f range between 0 , n-1, there's @ n different values each. therefore, maximum possible number of values can have n⁶. not tight bound, it's upper bound. gives runtime @ o(n⁶).

if want tighter bound, have work harder. this, i'm going use following fact:

1^k + 2^k + 3^k + ... + n^k = θ(n^k)

this sum of geometric series, comes from.

this means that

sum(f 0 n-1)    sum (e 0 f)       sum (d 0 e)           sum (c 0 d)               sum (b 0 c)                   sum (a 0 b)                       1  =  sum(f 0 n-1)      sum (e 0 f)         sum (d 0 e)             sum (c 0 d)                 sum (b 0 c)                     theta(b)  =  sum(f 0 n-1)      sum (e 0 f)         sum (d 0 e)             sum (c 0 d)                 theta(c^2)  =  sum(f 0 n-1)      sum (e 0 f)         sum (d 0 e)             theta(d^3)  =  sum(f 0 n-1)      sum (e 0 f)         theta(e^4)  =  sum(f 0 n-1)      theta(f^5)  = theta(n^6) 

hope helps!