/**
 * AlgDs, WS99, Aufgabe 30.
 * Zeitkomplexitaet eines Algorithmus.
 *
 * Ergebnis:
 * min. n*20-1
 * max. n*22-3
 *
 * @author Christian Semrau, 25.12.1999
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ChS_Aufg30 {
public static void main(String[] args){
// Datentypen:
int n; float[] a, b; float x, y; int z, i;

// Vorbedingungen:
n = 10; a = new float[n+1]; b = new float[n];
//for (int j=0; j<11; j++) a[j]=j;

int c = 0; // Zaehler

// hier geht's los:
x = 1.5f;
z = 0; 
i = 0;
c+=3;
// 3

c++;
while (i < n) {           // 1
  b[i] = (i+1) * a[i+1];  // 6
  i = i + 1;              // 2
  c+=9;
}
// n * 9 + 1

i = n - 1;
y = b[n-1];
c+=5;
// 5

c++;
while (i >= 1) {       // 1
  y = y * x + b[i-1];  // 5
  c+=6;

  if (y == 0){   // 1
	z = z + 1;   // 2
	a[i] = 0;    // 2
	c+=5;
  }else {
	a[i] = 1;    // 2
	c+=3;
  }
  // min. 3
  // max. 5

  i = i - 1;     // 2
  c+=2;
}
// min. (n-1)*11+1
// max. (n-1)*13+1

// Gesamt:
// min. 3+n*9+1+5+(n-1)*11+1 = n*20-1
// max. 3+n*9+1+5+(n-1)*13+1 = n*22-3
System.out.println(n+": "+(n*20-1)+"<="+c+"<="+(n*22-3));
}
} // ChS_Aufg30