Zeitkomplexität - Big O - anzeigen Zahlen von Intervall, das nicht in einer Datei sind

Question

ich das wissen will, ist die Zeitkomplexität dieses Codes (big-O):

(es liest eine Textdatei wie folgt: auf der ersten Zeile sind eine Nummer n und in der zweiten Zeile ist eine Liste mit aufsteigenden Nummern - Max. n Zahlen - und es zeigt alle Zahlen von 1 bis n, die nicht in der Textdatei ist)

#include <iostream> 
#include <fstream> 
using namespace std; 

int interval(int a, int b, int &ok) { 
    for(int i=1; i<(b-a); i++) { 
     cout << a+i << " "; ok=1; 
    } 
} 

int main() 
{ 
    int n=0, ok=0, a=0, b=0; 
    ifstream fisier("numere.in"); 
    fisier >> n; 
    while(fisier >> b) { b 
     interval(a,b,ok); 
     a = b; 
    } interval(b,n+1,ok); 
    if(ok == 0) cout << "Nu exista"; 
    return 0; 
} 

Ich denke es ist n * logn aber ich bin unsicher. Danke

Answer 1

Wenn Zahlen a1, a2, a3 ... a (n) dann,

zuerst geht es a1 mal dann in der nächsten Iteration a2-a1 mal, in der nächsten Iteration a3-a2 mal .. .. a (n) - a (n-1) mal. addieren das ergibt a (n) mal das ist O(n).