Sito Erastotenesa , złożoność obliczeniowa

Hej Wszystkim. Pierwszy post także jak coś źle to dajcie znać będę poprawiał :D Mam problem z tą metodą mianowicie nie rozumiem tej złożoności obliczeniowej i przez to nie wiem wgl jak się zabrać za tą metodę. Mógłby ktoś nakierować jakoś jak to zrobić, wytłumaczyć. Z góy wielkie dzięki. Program ma za zadanie wyliczać Liczby pierwsze zgodnie z algorytmem Sito Erastotenesa ma składać się z 3 metod odsiej() wyświetl() i sprawdź(). dwie wcześniejsze napisałem z tą mam problem.

  public boolean sprawdz (int k) 
  {
    // sprawdza czy k jest liczbą pierwsza
    // działa dla DOWOLNEGO k, również większego niż zadeklarowany wcześniej rozmiar sita "n"
    // działa niezależnie od tego, czy funkcja odsiej została wcześniej wywołana czy nie
    // ALE...
    // jeśli k<N i funkcja odsiej została wywołana, to funkcja sprawdź ma mieć złożoność obliczeniową O(1)
    // w pozostałych przypadkach akceptowalny jest O(n)
  }

Wklejam metody, które napisałem i które działają.

public void odsiej() {
		for (int i = 0; i < tab.length; i++) {
			tab[i] = i;
		}

		for (int i = 2; i < tab.length; i++) {

			for (int j = i; j < tab.length; j = j + i)
				if (tab[j] == i) {
					tab[j] = i;
				} else if (tab[j] != i) {
					tab[j] = 0;
				}

		}
	}

	public void wyswietl() {
		for (int i = 2; i < tab.length; i++) {
			if (tab[i] != 0) {
				System.out.println(tab[i]);
			}

		}
	}
	public boolean sprawdz(int k)
	{
		
		
	}

Jak już masz sporządzone sito tab o zakresie 2-n (swoja drogą, dziwnie je tworzysz), to dla liczby k <= n odczytujesz tab[k], Dla liczb k > n sprawdzasz w pętli czy istnieje dzielnik, da się to zrobić ze złożonością O(sqrt(n)). Musisz też w jakiejś zmiennej pamiętać czy wywołano już funkcję odsiej.

Gdy k<n to rozumiem ale nie mogę zrozumieć tej złożoności mógłbyś mi to jakoś wytłumaczyć zobrazować pewnie jest to łatwe a jakoś nie mogę tego pojąć.

Jeśli liczba k jest poza zakresem sita, to sprawdzenie czy jest liczbą pierwszą można zrobić przy pomocy takiej funkcji:

boolean isPrime(int k)
{
     if(k == 2)
     {
         return true;
     }
     double root = Math.sqrt(k);
     for(int i=2;i*i<=root;i++)
     {
          if((k % i) == 0)
          {
              return false;
          }
     }
     return true;
}

Kod w pętli wykona się najwyżej sqrt(k) razy, więc złożoność jest rzędu O(sqrt(N)), o ile k <= N.

Dzięki wielkie.
Myślę że rozumiem już o co chodzi .