Big O нотация

// Access array element by index
function getFirst(array $arr): mixed
{
    return $arr[0]; // Always one operation
}

// Access associative array element by key
function getValue(array $map, string $key): mixed
{
    return $map[$key]; // Average O(1)
}

// Access slice element by index
func getFirst(arr []int) int {
    return arr[0] // Always one operation
}

// Access map element by key
func getValue(m map[string]int, key string) int {
    return m[key] // Average O(1)
}

// Access list element by index
static T GetFirst<T>(List<T> arr)
{
    return arr[0]; // Always one operation
}

// Access dictionary element by key
static int GetValue(Dictionary<string, int> map, string key)
{
    return map[key]; // Average O(1)
}

# Access list element by index
def get_first(arr: list[int]) -> int:
    return arr[0]  # Always one operation

# Access dict element by key
def get_value(mapping: dict[str, int], key: str) -> int:
    return mapping[key]  # Average O(1)

// Binary search
function binarySearch(array $arr, int $target): int
{
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = intdiv($left + $right, 2);
        if ($arr[$mid] === $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1;
}

// Binary search
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

// Binary search
static int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}

# Binary search
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

// Find maximum in array
function findMax(array $arr): int
{
    $maxVal = $arr[0];
    foreach ($arr as $num) { // Go through each element
        if ($num > $maxVal) {
            $maxVal = $num;
        }
    }
    return $maxVal;
}

// Sum of elements
function total(array $arr): int
{
    return array_sum($arr); // Single pass through array
}

// Find maximum in slice
func findMax(arr []int) int {
    maxVal := arr[0]
    for _, num := range arr { // Go through each element
        if num > maxVal {
            maxVal = num
        }
    }
    return maxVal
}

// Sum of elements
func total(arr []int) int {
    sum := 0
    for _, v := range arr { // Single pass through slice
        sum += v
    }
    return sum
}

// Find maximum in array
static int FindMax(int[] arr)
{
    int maxVal = arr[0];
    foreach (int num in arr) // Go through each element
    {
        if (num > maxVal)
        {
            maxVal = num;
        }
    }
    return maxVal;
}

// Sum of elements
static int Total(int[] arr)
{
    return arr.Sum(); // Single pass through array
}

# Find maximum in list
def find_max(arr: list[int]) -> int:
    max_val = arr[0]
    for num in arr:  # Go through each element
        if num > max_val:
            max_val = num
    return max_val

# Sum of elements
def total(arr: list[int]) -> int:
    return sum(arr)  # Single pass through list

// Merge sort
function mergeSort(array $arr): array
{
    if (count($arr) <= 1) {
        return $arr;
    }

    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));   // log n levels
    $right = mergeSort(array_slice($arr, $mid));       // of recursion

    return merge($left, $right);                       // n operations per level
}

function merge(array $left, array $right): array
{
    $result = [];
    $i = 0;
    $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }
    while ($i < count($left)) {
        $result[] = $left[$i++];
    }
    while ($j < count($right)) {
        $result[] = $right[$j++];
    }
    return $result;
}

// Merge sort
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := mergeSort(arr[:mid])   // log n levels
    right := mergeSort(arr[mid:])  // of recursion

    return merge(left, right)      // n operations per level
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

// Merge sort
static List<int> MergeSort(List<int> arr)
{
    if (arr.Count <= 1)
    {
        return arr;
    }

    int mid = arr.Count / 2;
    var left = MergeSort(arr.GetRange(0, mid));                 // log n levels
    var right = MergeSort(arr.GetRange(mid, arr.Count - mid));  // of recursion

    return Merge(left, right);                                  // n operations per level
}

static List<int> Merge(List<int> left, List<int> right)
{
    var result = new List<int>(left.Count + right.Count);
    int i = 0, j = 0;
    while (i < left.Count && j < right.Count)
    {
        if (left[i] <= right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    result.AddRange(left.GetRange(i, left.Count - i));
    result.AddRange(right.GetRange(j, right.Count - j));
    return result;
}

# Merge sort
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # log n levels
    right = merge_sort(arr[mid:])  # of recursion

    return merge(left, right)      # n operations per level

def merge(left: list[int], right: list[int]) -> list[int]:
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

// Bubble sort
function bubbleSort(array $arr): array
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {           // n iterations
        for ($j = 0; $j < $n - 1 - $i; $j++) { // another n iterations
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
            }
        }
    }
    return $arr;
}

// Check for duplicates (naive approach)
function hasDuplicateNaive(array $arr): bool
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$i] === $arr[$j]) {
                return true;
            }
        }
    }
    return false;
}

// Bubble sort
func bubbleSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n; i++ {                // n iterations
        for j := 0; j < n-1-i; j++ {        // another n iterations
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

// Check for duplicates (naive approach)
func hasDuplicateNaive(arr []int) bool {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if arr[i] == arr[j] {
                return true
            }
        }
    }
    return false
}

// Bubble sort
static int[] BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)                 // n iterations
    {
        for (int j = 0; j < n - 1 - i; j++)     // another n iterations
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
            }
        }
    }
    return arr;
}

// Check for duplicates (naive approach)
static bool HasDuplicateNaive(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (arr[i] == arr[j])
            {
                return true;
            }
        }
    }
    return false;
}

# Bubble sort
def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n):                    # n iterations
        for j in range(n - 1 - i):        # another n iterations
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Check for duplicates (naive approach)
def has_duplicate_naive(arr: list[int]) -> bool:
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

// Naive Fibonacci
function fib(int $n): int
{
    if ($n <= 1) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2); // Two recursive calls!
}

// Naive Fibonacci
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // Two recursive calls!
}

// Naive Fibonacci
static int Fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    return Fib(n - 1) + Fib(n - 2); // Two recursive calls!
}

# Naive Fibonacci
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # Two recursive calls!

// This is all O(n), despite different number of passes
function example(array $arr): void
{
    foreach ($arr as $x) {     // n
        echo $x . "\n";
    }
    foreach ($arr as $x) {     // n
        echo $x . "\n";
    }
    foreach ($arr as $x) {     // n
        echo $x . "\n";
    }
}
// Total: 3n -> O(n)

// This is all O(n), despite different number of passes
func example(arr []int) {
    for _, x := range arr {     // n
        fmt.Println(x)
    }
    for _, x := range arr {     // n
        fmt.Println(x)
    }
    for _, x := range arr {     // n
        fmt.Println(x)
    }
}
// Total: 3n -> O(n)

// This is all O(n), despite different number of passes
static void Example(int[] arr)
{
    foreach (int x in arr)      // n
    {
        Console.WriteLine(x);
    }
    foreach (int x in arr)      // n
    {
        Console.WriteLine(x);
    }
    foreach (int x in arr)      // n
    {
        Console.WriteLine(x);
    }
}
// Total: 3n -> O(n)

# This is all O(n), despite different number of passes
def example(arr: list[int]) -> None:
    for x in arr:     # n
        print(x)
    for x in arr:     # n
        print(x)
    for x in arr:     # n
        print(x)

# Total: 3n -> O(n)

function example(array $arr): void
{
    // O(n)
    foreach ($arr as $x) {
        echo $x . "\n";
    }

    // O(n²)
    foreach ($arr as $i) {
        foreach ($arr as $j) {
            echo "$i $j\n";
        }
    }
}
// Total: O(n) + O(n²) = O(n²)

func example(arr []int) {
    // O(n)
    for _, x := range arr {
        fmt.Println(x)
    }

    // O(n²)
    for _, i := range arr {
        for _, j := range arr {
            fmt.Printf("%d %d\n", i, j)
        }
    }
}
// Total: O(n) + O(n²) = O(n²)

static void Example(int[] arr)
{
    // O(n)
    foreach (int x in arr)
    {
        Console.WriteLine(x);
    }

    // O(n²)
    foreach (int i in arr)
    {
        foreach (int j in arr)
        {
            Console.WriteLine($"{i} {j}");
        }
    }
}
// Total: O(n) + O(n²) = O(n²)

def example(arr: list[int]) -> None:
    # O(n)
    for x in arr:
        print(x)

    # O(n²)
    for i in arr:
        for j in arr:
            print(i, j)

# Total: O(n) + O(n²) = O(n²)

function process(array $arrA, array $arrB): void
{
    foreach ($arrA as $a) {     // O(a)
        echo $a . "\n";
    }
    foreach ($arrB as $b) {     // O(b)
        echo $b . "\n";
    }
}
// Total: O(a + b), NOT O(n)!

function cross(array $arrA, array $arrB): void
{
    foreach ($arrA as $a) {
        foreach ($arrB as $b) {
            echo "$a $b\n";
        }
    }
}
// Total: O(a * b)

func process(arrA, arrB []int) {
    for _, a := range arrA {     // O(a)
        fmt.Println(a)
    }
    for _, b := range arrB {     // O(b)
        fmt.Println(b)
    }
}
// Total: O(a + b), NOT O(n)!

func cross(arrA, arrB []int) {
    for _, a := range arrA {
        for _, b := range arrB {
            fmt.Printf("%d %d\n", a, b)
        }
    }
}
// Total: O(a * b)

static void Process(int[] arrA, int[] arrB)
{
    foreach (int a in arrA)     // O(a)
    {
        Console.WriteLine(a);
    }
    foreach (int b in arrB)     // O(b)
    {
        Console.WriteLine(b);
    }
}
// Total: O(a + b), NOT O(n)!

static void Cross(int[] arrA, int[] arrB)
{
    foreach (int a in arrA)
    {
        foreach (int b in arrB)
        {
            Console.WriteLine($"{a} {b}");
        }
    }
}
// Total: O(a * b)

def process(arr_a: list[int], arr_b: list[int]) -> None:
    for a in arr_a:     # O(a)
        print(a)
    for b in arr_b:     # O(b)
        print(b)

# Total: O(a + b), NOT O(n)!

def cross(arr_a: list[int], arr_b: list[int]) -> None:
    for a in arr_a:
        for b in arr_b:
            print(a, b)

# Total: O(a * b)

// Each time we halve n -> O(log n)
function halve(int $n): void
{
    while ($n > 1) {
        $n = intdiv($n, 2);
    }
}

// Each time we halve n -> O(log n)
func halve(n int) {
    for n > 1 {
        n = n / 2
    }
}

// Each time we halve n -> O(log n)
static void Halve(int n)
{
    while (n > 1)
    {
        n /= 2;
    }
}

# Each time we halve n -> O(log n)
def halve(n: int) -> None:
    while n > 1:
        n //= 2

// Dynamic array: append is usually O(1)
// But when array is full — copying O(n)
// Amortized: O(1) per operation
$arr = [];
for ($i = 0; $i < 1000000; $i++) {
    $arr[] = $i; // Amortized O(1)
}

// Dynamic slice: append is usually O(1)
// But when capacity is full — copying O(n)
// Amortized: O(1) per operation
arr := make([]int, 0)
for i := 0; i < 1000000; i++ {
    arr = append(arr, i) // Amortized O(1)
}

// List<T>: Add is usually O(1)
// But when the backing array is full — copying O(n)
// Amortized: O(1) per operation
var arr = new List<int>();
for (int i = 0; i < 1000000; i++)
{
    arr.Add(i); // Amortized O(1)
}

# Python list: append is usually O(1)
# But when the backing buffer is full — copying O(n)
# Amortized: O(1) per operation
arr: list[int] = []
for i in range(1_000_000):
    arr.append(i)  # Amortized O(1)