c++ - How do I calculate time complexity when having a break statement -

void f ( int a[], int n ) { // args: array a[ ] of size n    ( int k = n/2; k>0; k/=2 ) {      ( int j = 0; j< n; j++ ) {        if ( a[j] >= a[k] ) break;        else { int m = a[j]; a[j] = a[k]; a[k] = m; } }}} 

now, first loop 2 + log base-2 of n (2 + 2nd loop) . that's that.

the second (nested) loop problem. if best/worst case scenario, solution constant , linear, respectively. consider if-statement succeeds have time, complexity of nested loop?

what tried far 2 + (n/2)(2 + 1) + (n/2)(2 + 3) = 2 + 4n

in 2 initialization , comparison, , (n/2)(2 + 1) when if-statement succeeds, , (n/2)(2 + 3) else-statement.

but think entirely wrong. think i'm missing break statement ends loop, , becomes confusing. should n/2

what maybe finding out probability of algorithm go if , else statement. can average complexities summing them weighed chance of being executed. have average complexity (obviously not confused worst case complexity).

average = p * o(if-statement) + (1 - p) * o(else-statement) p probability if-statement executed, 0 => p >= 1.

edit: witn probability here don't imply randomness, see way of defining ratio between calls on if , else statement, , might able derive ratio predicate in if-statement.