# Laufzeit eines Algorithmus mittels Big Theta bestimmen



## gamma21 (13. Mrz 2019)

Ich bräuchte Hilfe/Bestätigung zur Laufzeit folgendes Pseudocodes:

```
x <-- 4*n
y <-- 0

   while x>0
       x <-- [x/2]
       for i=1,....,n
          y<-- y+x*i
```

Ich würde sagen der Code hat eine Laufzeit von Θ (n²). Kann mir das wer bestätigen?


----------



## httpdigest (13. Mrz 2019)

n * log2(n)

Die innere Schleife hat immer `n` Iterationen.
Die äußere Schleife teilt x immer durch 2 und läuft, solange x > 0.


----------



## gamma21 (13. Mrz 2019)

Danke für deine Hilfe.... wie komme ich aber in der äußeren Schleife auf log2(n)? Habe nun schon öfters in der Laufzeit eine log Funktion gesehen, kann mir aber nicht ganz erklären wie man auf diese kommt. Bin auch für hilfreiche Links dankbar.


----------



## Flown (13. Mrz 2019)

gamma21 hat gesagt.:


> Habe nun schon öfters in der Laufzeit eine log Funktion gesehen, kann mir aber nicht ganz erklären wie man auf diese kommt. Bin auch für hilfreiche Links dankbar.


Wenn du jedes mal die Hälfte von der Hälfte, .... nimmst, ist das nun mal die Logfunktion da sie die Umkehrung von 2^x ist (denn das wäre das Doppelte vom Doppelten, ...).


----------



## gamma21 (13. Mrz 2019)

Danke für die Antwort! Das ist eine gute Erklärung!


----------



## Flown (13. Mrz 2019)

gamma21 hat gesagt.:


> Danke für die Antwort! Das ist eine gute Erklärung!


Das ist nur sehr salopp ausgedrückt andere haben das ein wenig formaler beschrieben, wie in Wikipedia.


----------

