Matematyka dyskretna - Algorytm

[tyrla]

Pewien algorytm o dwóch danych wejściowych \(\displaystyle{ m}\) oraz \(\displaystyle{ n}\), które są liczbami naturalnymi, składa się z następujących kroków:
1) Krok początkowy o stałej liczbie czynności obliczeniowych.
2) Dla \(\displaystyle{ j = 1,…, m}\) powtarzaj czynności obliczeniowe o złożoności \(\displaystyle{ O(n)}\).
3) Jeżeli wyniki uzyskane w kroku 2) spełniają pewien warunek, wykonaj czynności
obliczeniowe o złożoności \(\displaystyle{ O(\log n)}\); w przypadku przeciwnym wykonaj inne czynności
obliczeniowe o złożoności \(\displaystyle{ O(n \cdot \log m)}\).
4) Po wykonaniu kroku 3) algorytm kończy się.
Podaj i uzasadnij, jaka jest złożoność obliczeniowa przedstawionego algorytmu?

[bartek118]

Przeanalizuj po kolei, co się dzieje. Złożoność to \(\displaystyle{ O(nm)}\).