0 Daumen
70 Aufrufe

Ich habe Unten einen Algorithmus, der prüft ob der Integer h im Array enthalten ist und ansonsten -1 ausgibt(Klausuraufgabe).

Nun soll ich die Laufzeit des Algorithmus bestimmen und bin mir dort relativ unsicher, da man es mit Vollständiger Induktion beweisen soll. Es ist gegeben, dass die Laufzeit in der Komplexitätsklasse O(n) liegt.

Da der Algorithmus rekursiv ist müsste aufgrund der 2 Aufrufe und Teilung des Problems durch 2 für das Master Theorem folgendes gelten:

T(n)=2T(n/2), wobei ich mir für c bzw. f/n relativ unsicher bin.

Wie kann ich dieses Erkenntnis nun für die Vollständige Induktion umformen?



Code:

public class Mysteryclass {
  public static int MYSTERY(int h, int[] array, int start, int end) {
      if (start == end) {
          if (array[start] == h) {
              return start;
          } else {
              return -1;
          }
      }
      else {
          int x = (start + end + 1) / 2;
          int i = MYSTERY(h, array, start, x - 1);
          int j = MYSTERY(h, array, x, end);

          if (i != -1) {
              return i;
          }
          else {
              return j;
          }
      }
  }
}
von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community