Lauzeitkomplexität von Algorithmen

Aufrufe: 243     Aktiv: 27.02.2023 um 16:10

0
Hallo ich habe bei einer Aufgabe zur Laufzeitkomplexität von Algorithmen ein Problem. Ich habe Folgenden Algorithmus als Pseudocode gegeben:
Input: n ∈ Z, mit n = 2^m
Output: eine gewisse Ausgabe
1: i ← n
2: j ← 1
3: k ← 0
4: while i > 0 do
5:    while j < n do
6:        while k < j do
7:          Eine von {i, j, k} unabhängige Operation;
8:          k ← k + 1
9:        end while
10:     j ← 2 · j
11:   end while
12: i ← i − 1
13: end while
14: return Liste der Ergebnisse

Ich soll zeigen das die Laufzeitkomplexität Θ(n^2)

Ich sehe das die erste Schleife O(n) ist da die erste Schleife unabhängig von der zweiten und dritten ist müssten die zweite und dritte also O(n) sein damit der gesamte Algorithmus O(n^2) ist dies sehe ich jedoch noch nicht so wirklich kann mir vielleicht jemand behilflich sein und erklären warum die zweite und dritte Schleife, welche ja nicht unabhängig voneinander sind O(n) ist ?
Diese Frage melden
gefragt

Punkte: 16

 

Alles klar gut zu wissen danke!   ─   henry_99 27.02.2023 um 16:10
Kommentar schreiben
0 Antworten