3. Big O(√n)

O(√n) ist eine weniger häufige Zeitkomplexität und tritt bei Algorithmen auf, die etwa die Quadratwurzel der Eingabegröße verarbeiten.

Diese Komplexität bedeutet, dass die Laufzeit mit der Wurzel der Eingabegröße wächst. Ein Beispiel sind Algorithmen zur Primzahlprüfung (Trial Division), bei denen die Suche nur bis zur Quadratwurzel der Zahl durchgeführt wird.

Python-Beispiel für O(√n):

Hier eine einfache Primzahlprüfung, die nur bis zur Quadratwurzel der Zahl iteriert. Da für die Schleifenanzahl nur Werte bis √n geprüft werden, ist die Laufzeit O(√n).

import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False  # Teilbar, daher keine Primzahl
    return True  # Keine Teiler gefunden, daher Primzahl

# Verwendung
print(is_prime(29))  # Ausgabe: True
print(is_prime(30))  # Ausgabe: False

Java-Beispiel für O(√n):

Hier eine ähnliche Primzahlprüfung in Java. Die Programmierung Methode isPrime iteriert nur bis zur Quadratwurzel der Zahl n, wodurch sie eine Laufzeit von O(√n) hat.

public class Main {
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;  // Teilbar, daher keine Primzahl
            }
        }
        return true;  // Keine Teiler gefunden, daher Primzahl
    }

    public static void main(String[] args) {
        System.out.println(isPrime(29));  // Ausgabe: true
        System.out.println(isPrime(30));  // Ausgabe: false
    }
}

Da die Schleife nur bis zur Quadratwurzel von n läuft, haben beide Beispiele eine Zeitkomplexität von O(√n).