Notacja duzego O

Question

mam pseudocode wygladajacy w nastepujacy sposob:

for i in range n
     for j i range p 
          if i == j 
             boolean = true

     if boolean == true 
          y = y + 1
     else 
         x = x + 1

jaka jest notacja duzego O?     

Glownie moje pytanie dotyczy ile razy if statementy sa wykonywane. 

 

 

Answer 1

Są dwie zagnieżdżone pętle, bez żadnych przerwań czy manipulacji zmiennymi iterującymi w środku - O(n*p).

Do pierwszego ifa pętla wejdzie min(n,p).

Do drugiego równo n razy, bo nigdzie nie ustawiasz boolean na false. Gdybyś ustawiał na początku pętli zewnętrznej to byłoby max(n,p) - min(n,p).