Complexity and Memory

Lab contests

There are 12 lab contests across the semester, one per week starting from week 3, plus a TSIS assignment each week. Every contest carries its own point value — the syllabus lists them next to the week.

The rule

LabContest 1 contains 10 problems, A to J, and is worth 3 points. Solve as many as you can on ejudge.

Two weeks after the lab opens a separate defence contest runs. It holds 2 problems taken from this same list of 10 — the same two for everyone — and you solve them there, on the spot, from scratch.

Your result on the defence contest, as a percentage, is multiplied by the percentage of the lab you solved.

Formula

Rounded to two decimals. The same formula applies to every lab contest — only L and the number of problems change.

What the course consists of

• Syllabus, covered topics, laboratory works
• Midterm, endterm, final examinations
• Ejudge.kz system, GitHub, defence rules
• Labs — practice lessons to help solving labs

Thirteen lectures

The problem and the naive approach

Problem: find the largest positive integer that divides both numbers a and b.

Naive approach

• Check all numbers from min(a, b) down to 1
• Time complexity: O(min(a, b))
• Inefficient for large numbers

Example

• For small numbers like GCD(12, 18) it works fine: at most 12 checks — it actually stops at 6 after 7
• For large primes like GCD(1000000007, 1000000009) it needs about 1 billion checks
• With large numbers this approach takes an extremely long time

The Euclidean algorithm

On the board:

gcd(12, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6
gcd(48, 180) = gcd(180, 48) = gcd(48, 36) = gcd(36, 12) = gcd(12, 0) = 12

Implementation

int gcd(int a, int b) {
    for (int i = min(a, b); i >= 1; --i) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}

int gcd2(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd2(b, a % b);
}

// Iterative version
int gcd1(int a, int b) {
    while (a > 0 && b > 0) {
        if (a > b)
            a = a % b;
        else
            b = b % a;        
    }

    // if (a > 0)
    //     return b;
    // return a;
    return a + b;
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    for (int i = min(a, b); i >= 1; --i) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}

int gcd2(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd2(b, a % b);
}

// Iterative version
int gcd1(int a, int b) {
    while (a > 0 && b > 0) {
        if (a > b)
            a = a % b;
        else
            b = b % a;        
    }

    // if (a > 0)
    //     return b;
    // return a;
    return a + b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd2(a, b) << endl;
    return 0;
}

12 18

6

Another version · with long long

The same three functions on long long. That is what problem A needs: a and b go up to 10¹⁸, which does not fit into int.

#include <iostream>
#define ll long long

using namespace std;

ll gcd1(ll a, ll b) {
    for (ll i = min(a, b); i >= 1; --i) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return 1;
}

ll gcd2(ll a, ll b) {
    if (b == 0) {
        return a;
    }
    return gcd2(b, a % b);
}

ll gcd3(ll a, ll b) {
    while (a > 0 && b > 0) {
        if (a > b) {
            a = a % b;
        } else {
            b = b % a;
        }
    }
    return a + b;
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << gcd1(a, b) << endl;
    return 0;
}

12 18

6

The problem and the idea

Problem: calculate aⁿ efficiently.

Naive approach

• Multiply a by itself n times
• Time complexity: O(n)
• Inefficient for large exponents

Binary exponentiation

• Based on the property aⁿ = (a^n/2)² if n is even
• If n is odd: aⁿ = a × aⁿ⁻¹
• Time complexity: O(log n)

Algorithm

1. If n = 0, return 1
2. If n is even: result = (a^n/2)²
3. If n is odd: result = a × aⁿ⁻¹
4. Use recursion or iteration

Example · 2¹⁰

2¹⁰ = (2⁵)² = (2 × 2⁴)² = (2 × (2²)²)² = (2 × 4²)² = (2 × 16)² = 32² = 1024

What the recursive code below actually multiplies, in order:

2^1 = 2 × 1 = 2
2^2 = 2 × 2 = 4
2^4 = 4 × 4 = 16
2^5 = 2 × 16 = 32
2^10 = 32 × 32 = 1024

4 real multiplications instead of 10 — the first line, 2 × 1, is the base case and costs nothing.

Implementation

// Recursive version
long long binpow(long long a, long long n) {
    if (n == 0)
        return 1;
    if (n % 2 == 0) {
        long long half = binpow(a, n / 2);
        return half * half;
    } else {
        return a * binpow(a, n - 1);
    }
}

// Iterative version
long long binpow_iter(long long a, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            result *= a;
        }
        a *= a;
        n /= 2;
    }
    return result;
}

// Example usage
int main() {
    long long base, exp;
    cin >> base >> exp;
    cout << "Result: " << binpow(base, exp) << endl;
    cout << "Result (iterative): " << binpow_iter(base, exp) << endl;
    return 0;
}

2 10

Result: 1024
Result (iterative): 1024

Another version · modulo m, and the naive loop

For problem B the answer is aⁿ mod m. The naive loop for comparison:

ll pow_a_b(ll a, ll b) {
    if (b == 0) 
        return 1;
    ll result = 1;
    for (ll i = 0; i < b; ++i) 
        result *= a;
    return result;
}

and binary exponentiation modulo m:

ll bin_pow(ll a, ll b, ll m) {
    if (b == 0) 
        return 1 % m;   // fixed: for m = 1 the answer is 0, not 1
    if (b % 2 == 0) {
        ll half = bin_pow(a, b / 2, m);
        return (half * half) % m;
    } else {
        return (a % m * bin_pow(a, b - 1, m)) % m;   // fixed: a up to 10^18 overflows without % m
    }
}

#include <iostream>
#define ll long long
using namespace std;

ll bin_pow(ll a, ll b, ll m) {
    if (b == 0) 
        return 1 % m;   // fixed: for m = 1 the answer is 0, not 1
    if (b % 2 == 0) {
        ll half = bin_pow(a, b / 2, m);
        return (half * half) % m;
    } else {
        return (a % m * bin_pow(a, b - 1, m)) % m;   // fixed: a up to 10^18 overflows without % m
    }
}

ll pow_a_b(ll a, ll b) {
    if (b == 0) 
        return 1;
    ll result = 1;
    for (ll i = 0; i < b; ++i) 
        result *= a;
    return result;
}

int main() {
    ll a, b, m;
    cin >> a >> b >> m;
    cout << bin_pow(a, b, m) << endl;
    return 0;
}

2 10 1000000000

1024

The problem and the naive approach

Problem: find all prime numbers up to n efficiently.

Naive approach

• Check each number for primality individually
• Time complexity: O(n√n)

Example · primes up to 30

Start with [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
Cross out multiples of 2: [2,3,5,7,9,11,13,15,17,19,21,23,25,27,29]
Cross out multiples of 3: [2,3,5,7,11,13,17,19,23,25,29]
Cross out multiples of 5: [2,3,5,7,11,13,17,19,23,29]
6² = 36 > 30 — stop, everything left is prime

Result: [2,3,5,7,11,13,17,19,23,29]

Complexity and the algorithm

• Time complexity: O(n log log n) — much better than the naive approach
• Space complexity: O(n)

1. Create a boolean array is_prime[0..n], initialize all as true
2. Set is_prime[0] = is_prime[1] = false
3. For each number i from 2 to √n: if is_prime[i] is true, mark all multiples of i, starting from i², as false
4. The remaining true values are primes

Another version · trial division and the sieve side by side

Testing one number by dividing up to √n:

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

and the sieve — here 0 means "prime", 1 means "crossed out":

vector<int> primes(int n) {
    vector<int> is_prime(n + 1, 0);
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = 1;
            }
        }
    }
    return is_prime;
}

#include <iostream>
#include <vector>

using namespace std;

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

vector<int> primes(int n) {
    vector<int> is_prime(n + 1, 0);
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = 1;
            }
        }
    }
    return is_prime;
}

int main() {
    int n;
    cin >> n;
    // for (int i = 1; i <= n; i++) {
    //     if (is_prime(i)) {
    //         cout << i << " ";
    //     }
    // }
    vector<int> p = primes(n);
    for (int i = 2; i <= n; i++) {
        if (p[i] == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

30

2 3 5 7 11 13 17 19 23 29

Another version · the sieve returns the list of primes

#include <iostream>
#include <vector>

using namespace std;

vector<int> prime_numbers(int n) {
    int a[n + 1];
    for (int i = 0; i <= n; i++)
        a[i] = 0;
    for (int i = 2; i * i <= n; i++) {
        if (a[i] == 0) {
            for (int j = i * i; j <= n; j+=i)
                a[j] = 1;
        }
    }
    vector<int> result;
    for (int i = 2; i <=n; i++)
        if (a[i] == 0)
            result.push_back(i);
    return result;

}

int main() {
    int n;
    cin >> n;
    vector<int> primes = prime_numbers(n);
    for (int i = 0; i < primes.size(); i++)
        cout << primes[i] << " ";
    return 0;
}

30

2 3 5 7 11 13 17 19 23 29

Examples

60 = 2 × 2 × 3 × 5
60 ÷ 2 = 30 → ÷ 2 = 15 → ÷ 3 = 5 → 5 is prime

210 = 2 × 3 × 5 × 7
210 ÷ 2 = 105 → ÷ 3 = 35 → ÷ 5 = 7 → 7 is prime

Basic implementation

#include <iostream>
using namespace std;

void primeFactorization(int n) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    if (n > 1) cout << n; // remaining prime
    cout << endl;
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    cout << "Prime factors: ";
    primeFactorization(num);
    return 0;
}

60

Enter a number: Prime factors: 2 2 3 5

Worst case: O(√n) — trial division.

Faster · sieve + precomputed primes

// Generate primes up to limit using Sieve of Eratosthenes
vector<int> sieve(int limit) {
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

// Prime factorization using precomputed primes
void primeFactorization(int n, const vector<int>& primes) {
    int temp = n;
    for (int p : primes) {
        if (p * p > n) break; // stop when p > sqrt(n)
        while (n % p == 0) {
            cout << p << " ";
            n /= p;
        }
    }
    if (n > 1) cout << n; // remaining prime factor
    cout << endl;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Generate primes up to limit using Sieve of Eratosthenes
vector<int> sieve(int limit) {
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

// Prime factorization using precomputed primes
void primeFactorization(int n, const vector<int>& primes) {
    int temp = n;
    for (int p : primes) {
        if (p * p > n) break; // stop when p > sqrt(n)
        while (n % p == 0) {
            cout << p << " ";
            n /= p;
        }
    }
    if (n > 1) cout << n; // remaining prime factor
    cout << endl;
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    // Precompute primes up to sqrt(num)
    int limit = (int)(sqrt(num)) + 1;
    vector<int> primes = sieve(limit);

    cout << "Prime factors of " << num << ": ";
    primeFactorization(num, primes);

    return 0;
}

210

Enter a number: Prime factors of 210: 2 3 5 7

Efficiency

• Sieve: O(n log log n), once
• Factorization: O(π(√n)), where π(x) is the number of primes ≤ x — much fewer than √n divisions

Why complexity matters

• Sorting 10 numbers → both good and bad algorithms finish instantly.
• Sorting 10 million numbers → slow algorithms take hours, fast ones finish in seconds.
• We use complexity analysis to predict how runtime and memory grow as n increases.

Big-O describes the upper bound on the growth rate — how fast runtime or memory usage can grow in the worst case.

Key principles

• Ignore constant factors — 2n or 5n, it is still O(n)
• Ignore less significant terms — n² + n → O(n²), because n² dominates for large n

Common time complexities

Example of O(2ⁿ) — very inefficient

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // Very slow for large n
}

Extra memory beyond the input

• O(1) → constant extra space (variables, counters)
• O(n) → memory proportional to n (arrays, hash maps)
• O(n²) → large 2D matrices, graph adjacency matrices

Core operations

• push(item) — add an item to the top — O(1)
• pop() — remove the top item — O(1)
• top() / peek() — view the top item without removing it — O(1)
• empty() — check if the stack is empty — O(1)
• size() — get the number of elements — O(1)

C++ implementation using the STL

// C++ built-in stack
#include <iostream>
#include <stack>
using namespace std;

int main() {
   stack<int> st;
   st.push(10);
   st.push(20);
   st.push(15);
   st.push(1);

   cout << st.top() << endl; // 1
   st.pop();
   st.pop();
   cout << st.top() << endl; // 20
   cout << st.size() << endl;
   cout << st.empty();
   return 0;
}

1
20
2
0

Another version · Stack and Queue on linked nodes

No STL: each element is a Node with a pointer to the next one. The stack pushes and pops at the head; the queue keeps both front and rear.

#include <iostream>
#include <stack>

using namespace std;

class Node {
    public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = nullptr;
    }
};

class Stack {

    public:
    Node* top;
    int sz;
    Stack() {
        top = NULL;
        sz = 0;
    }

    void push(int val) {
        Node* newNode = new Node(val);
        newNode->next = top;
        top = newNode;
        sz++;
    }

    void pop() {
        if (top == NULL) 
            return;
        Node* temp = top;
        top = top->next;
        delete temp;
        sz--;
    }

    int peek() {
        if (top == NULL) 
            return -1; // or throw an exception
        return top->data;
    }

    int size() {
        return sz;
    }

    int empty() {
        return sz == 0;
    }
};

class Queue {
    public:

    Node* front;
    Node* rear;
    Queue() {
        front = NULL;
        rear = NULL;
    }

    void push(int val) {
        Node* newNode = new Node(val);
        if (rear == NULL) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }
    void pop() {
        if (front == NULL) 
            return;
        Node* temp = front;
        front = front->next;
        if (front == NULL) 
            rear = NULL;
        delete temp;
    }
    int peek() {
        if (front == NULL) 
            return -1; // or throw an exception
        return front->data;
    }
    int empty() {   
        return front == NULL;
    }
    int size() {
        int count = 0;
        Node* current = front;
        while (current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }

};

int main() {
    // stack<int> st;
    // st.push(10);
    // st.push(20);
    // st.push(30);
    // st.push(40);
    // cout << st.top() << endl;
    // st.pop();
    // cout << st.top() << endl;
    // cout << st.size() << endl;
    // cout << st.empty() << endl; 
    // Node* node1 = new Node(10);
    // Node* node2 = new Node(20);
    // Node* node3 = new Node(30);
    // node1->next = node2;
    // node2->next = node3;
    // cout << node1->data << " " << node2->data << " " << node3->data << endl;
    // cout << node1->next->next->data << endl;
    Stack *st = new Stack();
    st->push(10);
    st->push(20);   
    st->push(30);   
    st->push(40);   
    cout << st->peek() << endl;
    st->pop();
    cout << st->peek() << endl;
    cout << st->size() << endl;
    cout << st->empty() << endl;
    return 0;
}

40
30
3
0

Problem to topic