Data Structures, Algorithms, and Analysis: Complete Study Notes

Data Structures Foundations and Classification

• Data Definition: A collection of raw facts.

• Data Structure: A specialized format for organizing, storing, and representing logical relationships existing between individual data elements in computer memory.

• Key Characteristics of Data Structures:

  • Logical representation of data in computer memory.

  • Logical relationships defined between various data elements.

  • Facilitates efficient manipulation and processing of stored data elements.

Need for Data Structures

Modern applications process growing volumes of data, introducing key computational challenges:

• Processor Speed Limits: High-speed processing is required for massive datasets. As datasets scale to billions of records per entity, processor execution speeds hit physical limits if data is unorganized.

• Data Search Scalability: Searching through an unindexed inventory of $10^6$ items sequentially requires up to $10^6$ comparisons per query, causing severe application slowdowns.

• Simultaneous Requests: High-traffic web servers processing thousands of concurrent user queries can fail without structured data organization.

Advantages of Data Structures

• Efficiency: Choosing an optimal data structure drastically reduces execution time (e.g., using ordered arrays, binary search trees, or hash tables instead of linear arrays for lookup operations).

• Reusability: Once implemented, data structure modules can be compiled into libraries and reused across different client applications.

• Abstraction: Data structures implement Abstract Data Types (ADTs), providing a clean interface to client code while hiding implementation details.

Data Structures Classification

• Primitive Data Structures: Predefined data types built directly into the programming language (e.g., int, char, float, double).

• Non-Primitive Data Structures: Complex data structures constructed from primitive data types:

  • Linear Data Structures: Data elements arranged sequentially where each element is connected to its previous and next adjacent elements (e.g., Array, Stack, Queue, Linked List).

  • Non-Linear Data Structures: Data elements organized hierarchically or in interconnected networks (e.g., Trees, Graphs).

Basic Data Structure Operations

• Traversing: Accessing each data element exactly once to process or display it.

• Searching: Finding the memory location of an element matching a given key value.

• Insertion: Adding a new data element into the structure.

• Deletion: Removing an existing data element from the structure.

• Sorting: Arranging data elements in a specific numerical or lexicographical order.

• Merging: Combining elements from two different structures into a single structure.

Linear Data Structures: Arrays

Array Characteristics and Types

• Definition: An array is a linear collection of fixed number of homogeneous data elements stored at contiguous memory locations under a single variable name.

• Key Characteristics:

  • Elements are referenced using a single array name and distinguished by index values.

  • Indexing starts at $0$ in C language.

  • Array name serves as a pointer to the first element (base address).

  • Array size must be a constant expression determined at compile-time.

  • Memory is allocated contiguously at runtime; no automatic boundary checking is performed by low-level languages like C.

• Array Types:

  • One-dimensional Array (array[]): A linear group of homogeneous elements (e.g., {2, 5, 6, 1, 9}).

  • Multi-dimensional Array (array[][].[]): An array of arrays where each element is itself an array (e.g., a matrix or group of strings like {"Ajay", "Vikas", "Amit", "Sumit"}).

Memory Representation and Addressing Calculations

One-Dimensional Array Addressing Formula

Given an array $A$ with base address $B$, word size (element memory size) $W$, index $k$, and lower bound $LB$ (default $0$):

$\text{Address of } A[k] = B + W \times k$

$\text{Address of } A[k] = B + W \times (k - LB)$

Worked Examples:

For an array arr[5] = {2, 6, 7, 3, 8} with base address $B = 6000$ and word size $W = 2\,\text{bytes}$:

• Address of arr[2]: $6000 + 2 \times 2 = 6004$

• Address of arr[4]: $6000 + 2 \times 4 = 6008$

Multi-Dimensional Array Memory Layout

Two-dimensional arrays are stored linearly in memory using two mapping strategies:

• Row-Major Order: Elements are stored row by row sequentially.

• Column-Major Order: Elements are stored column by column sequentially.

Address Computation Formulas for 2D Array $A[m][n]$:

• Row-Major Order: $\text{Address of } A[i][j] = B + W \times (n \times (i - LBR) + (j - LBC))$

• Column-Major Order: $\text{Address of } A[i][j] = B + W \times (m \times (j - LBC) + (i - LBR))$

Where:

• $B$ = Base Address

• $W$ = Word size (bytes per element)

• $m$ = Total number of rows

• $n$ = Total number of columns

• $i, j$ = Target row and column indices

• $LBR$ = Lower bound of row index

• $LBC$ = Lower bound of column index

Comprehensive Worked Example:

Given a $10 \times 12$ matrix implemented as A[10][12] with base address $B = 200$, word size $W = 2\,\text{bytes}$, and lower bounds $LBR = 1, LBC = 1$ ($m = 10, n = 12$):

1. Compute Address of $A[4][7]$:

   • Row-Major Order: $\text{Address} = 200 + 2 \times (12 \times (4 - 1) + (7 - 1)) = 200 + 2 \times (12 \times 3 + 6) = 200 + 2 \times 42 = 284$

   • Column-Major Order: $\text{Address} = 200 + 2 \times (10 \times (7 - 1) + (4 - 1)) = 200 + 2 \times (10 \times 6 + 3) = 200 + 2 \times 63 = 326$

2. Compute Address of $A[5][6]$:

   • Row-Major Order: $\text{Address} = 200 + 2 \times (12 \times (5 - 1) + (6 - 1)) = 200 + 2 \times (12 \times 4 + 5) = 200 + 2 \times 53 = 306$

   • Column-Major Order: $\text{Address} = 200 + 2 \times (10 \times (6 - 1) + (5 - 1)) = 200 + 2 \times (10 \times 5 + 4) = 200 + 2 \times 54 = 308$

Array Algorithms and C Implementations

Array Traversal

Algorithm TRAVERSE(LA, LB, UB):

1. Set $K := LB$

2. Repeat Steps 3 and 4 while $K \le UB$

3. Apply PROCESS to $LA[K]$

4. Set $K := K + 1$

5. Exit

#include <stdio.h>
#include <conio.h>

void traverse(int *array, int size) {
    int i;
    for(i = 0; i < size; i++) {
        printf("arr[%d] = %d\n", i, array[i]);
    }
}

void main() {
    int arr[5] = {2, 6, 7, 3, 8};
    int N = 5;
    clrscr();
    printf("Press any key to perform array traversal and display its elements: \n\n");
    getch();
    traverse(arr, N);
    getch();
}

Array Insertion

Algorithm INSERT(LA, N, K, ITEM):

1. Set $J := N$

2. Repeat Steps 3 and 4 while $J \ge K$

3. Set $LA[J + 1] := LA[J]$ (Shift element downward)

4. Set $J := J - 1$

5. Set $LA[K] := ITEM$

6. Set $N := N + 1$

7. Exit

Array Deletion

Algorithm DELETE(LA, N, K, ITEM):

1. Set $ITEM := LA[K]$

2. Repeat for $J = K$ to $N - 1$:

   • Set $LA[J] := LA[J + 1]$ (Shift element upward)

3. Set $N := N - 1$

4. Exit

Linear Search

Linear search scans elements sequentially from index $0$ to $N-1$. A sentinel can be placed at $DATA[N+1]$ to streamline loop condition testing.

Algorithm LINEAR(DATA, N, ITEM, LOC):

1. Set $DATA[N + 1] := ITEM$ (Insert sentinel)

2. Set $LOC := 1$

3. Repeat while $DATA[LOC] \neq ITEM$:

   • Set $LOC := LOC + 1$

4. If $LOC = N + 1$, then Set $LOC := 0$ (Search unsuccessful)

5. Exit

• Time Complexity: Worst-case $O(n)$, Best-case $O(1)$, Average-case $\approx \frac{n+1}{2}$ comparisons.

Binary Search

Binary Search operates on a sorted array by halving the search space recursively or iteratively.

• Prerequisites:

  • Array must be in sorted order.

  • Direct indexing/random access must take $O(1)$ time.

Algorithm BINARY(DATA, LB, UB, ITEM, LOC):

1. Set $BEG := LB, END := UB, MID := \lfloor \frac{BEG + END}{2} \rfloor$

2. Repeat Steps 3 and 4 while $BEG \le END$ and $DATA[MID] \neq ITEM$

3. If $ITEM < DATA[MID]$, then Set $END := MID - 1$; Else Set $BEG := MID + 1$

4. Set $MID := \lfloor \frac{BEG + END}{2} \rfloor$

5. If $DATA[MID] = ITEM$, then Set $LOC := MID$; Else Set $LOC := \text{NULL}$

6. Exit

• Limitations of Binary Search:

  • Dataset must be strictly sorted; initial sorting costs $O(n \log(n))$.

  • Maintaining sorted order during frequent insertions and deletions is costly ($O(n)$ shifting).

  • Inefficient for pointer-based Linked Lists because finding the middle element takes $O(n)$ time.

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order, bubbling the largest unsorted element to its correct end position in each pass.

Algorithm BUBBLE(DATA, N):

1. Repeat Steps 2 and 3 for $K = 1$ to $N - 1$

2. Set $PTR := 1$

3. Repeat while $PTR \le N - K$

   • If $DATA[PTR] > DATA[PTR + 1]$, then Swap $DATA[PTR]$ and $DATA[PTR + 1]$

   • Set $PTR := PTR + 1$

4. Exit

• Bubble Sort Complexity Derivation: Number of comparisons $f(n)$ across passes:

  $f(n) = (n - 1) + (n - 2) + (n - 3) + \dots + 2 + 1 = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2} = O(n^2)$

Stacks

Definition and Abstract Data Type Properties

• Definition: A stack is a linear data structure operating on the Last-In-First-Out (LIFO) principle. All insertions (push) and deletions (pop) occur restrictedly at a single designated end called top.

• Real-World Examples: Stack of books, stack of clothes, stack of plates.

Array vs. Stack Comparison

Stack Operations and Memory Representation

• Memory Allocation: Contiguous array block managed via pointer TOP.

• Operations:

  • Push: Increments TOP by $1$ and stores new element at STACK[TOP]. Check for TOP == MAXSTK (OVERFLOW).

  • Pop: Retrieves element at STACK[TOP] and decrements TOP by $1$. Check for TOP == 0 or NULL (UNDERFLOW).

Stack Algorithms

Algorithm PUSH(STACK, TOP, MAXSTK, ITEM):

1. If $TOP = MAXSTK$, then Print "OVERFLOW", and Return

2. Set $TOP := TOP + 1$

3. Set $STACK[TOP] := ITEM$

4. Return

Algorithm POP(STACK, TOP, ITEM):

1. If $TOP = 0$, then Print "UNDERFLOW", and Return

2. Set $ITEM := STACK[TOP]$

3. Set $TOP := TOP - 1$

4. Return

Applications of Stacks

• String Reversal (Pushing chars sequentially, then popping into target string)

• Undo/Redo mechanisms in text editors

• Subroutine call stack and Recursion execution

• Graph traversal algorithms (Depth First Search / DFS)

• Expression evaluation and parsing

Arithmetic Expressions and Polish Notation

Infix expressions like $(A + B) \times C$ depend on operator precedence and parentheses. Polish notations eliminate parentheses ambiguity.

• Infix Notation: Operator between operands ($A + B$).

• Prefix (Polish) Notation: Operator precedes operands ($+AB$).

• Postfix (Reverse Polish) Notation: Operator follows operands ($AB+$).

Operator Precedence Hierarchy

1. Highest: Exponentiation (^)

2. Next Highest: Multiplication (*) and Division (/)

3. Lowest: Addition (+) and Subtraction (-)

Infix, Prefix, and Postfix Equivalence Table

Evaluation of Postfix Expression Algorithm

To evaluate postfix expression $P$:

1. Append sentinel ")" to end of $P$

2. Scan $P$ left to right until ")" is encountered

3. If an operand is scanned, push onto STACK

4. If an operator $\otimes$ is scanned:

   • Pop top element $A$ and next-to-top element $B$

   • Evaluate result $B \otimes A$

   • Push result back onto STACK

5. Set VALUE equal to top element of STACK and exit

Worked Evaluation Example:

Evaluate $5 \times (6 + 2) - 12 / 4$ Postfix representation: 5, 6, 2, +, *, 12, 4, /, -

Transforming Infix to Postfix Algorithm (POLISH(Q, P))

1. Push ( onto STACK and append ) to end of infix expression $Q$

2. Scan $Q$ left-to-right until STACK is empty:

   • If operand: add to postfix string $P$

   • If (: push onto STACK

   • If operator $\otimes$: repeatedly pop operators from STACK with same or higher precedence than $\otimes$ and add to $P$; then push $\otimes$ onto STACK

   • If ): repeatedly pop from STACK to $P$ until ( is popped; discard (

Detailed Transformation Step Trace:

Infix: $A + (B \times C - (D / E \hat{} F) \times G) \times H$ Output Postfix $P$: A B C * D E F ^ / G * - H * +

Queues

Definition and Core Concepts

• Definition: A Queue is a linear data structure operating on the First-In-First-Out (FIFO) principle. Elements enter at the Rear end and leave from the Front end.

• Applications: CPU scheduling, shared printer queues in computer networks, memory buffer management.

Standard Queue Operations

• Insert (Enqueue): Receives item, increments rear pointer, stores item at new rear location.

• Delete (Dequeue): Retrieves front item, increments front pointer to point to next element.

Circular Queues

Linear array implementations waste space when elements are deleted because front shifts right, leaving unused memory at lower indices. A Circular Queue connects start (index 0) to end (index N-1) logically.

Circular Queue Algorithms

Procedure QINSERT(QUEUE, N, FRONT, REAR, ITEM):

1. If $(FRONT = 1 \text{ AND } REAR = N)$ OR $(FRONT = REAR + 1)$, then Write "OVERFLOW", Return

2. If $FRONT = \text{NULL}$, then Set $FRONT := 1, REAR := 1$ Else if $REAR = N$, then Set $REAR := 1$ Else Set $REAR := REAR + 1$

3. Set $QUEUE[REAR] := ITEM$

4. Return

Procedure QDELETE(QUEUE, N, FRONT, REAR, ITEM):

1. If $FRONT = \text{NULL}$, then Write "UNDERFLOW", Return

2. Set $ITEM := QUEUE[FRONT]$

3. If $FRONT = REAR$, then Set $FRONT := \text{NULL}, REAR := \text{NULL}$ (Queue empty) Else if $FRONT = N$, then Set $FRONT := 1$ Else Set $FRONT := FRONT + 1$

4. Return

Priority Queues

• Definition: A queue variant where each element carries an assigned priority. Elements are dequeued based on priority rather than arrival time.

• Rules:

  1. Higher priority elements are deleted before lower priority elements.

  2. Equal priority elements are processed on a First-In-First-Out (FIFO) basis.

• Implementation Options:

  • Unsorted insertion + search for highest priority element during deletion.

  • Sorted insertion (elements inserted into sorted position by priority) + sequential deletion from front.

Double-Ended Queue (Deque)

• Definition: A linear structure where insertions and deletions can occur at both ends (Front and Rear), but not in the middle.

• Deque Categories:

  • Input-Restricted Deque: Deletion permitted at both ends; insertion restricted to one end.

  • Output-Restricted Deque: Insertion permitted at both ends; deletion restricted to one end.

• Four Basic Operations: InsertFront(x), InsertRear(x), DeleteFront(), DeleteRear().

Deque Algorithms

InsertFront(x):

1. If $(front = 0 \text{ AND } rear = MAX-1) \text{ OR } (front = rear + 1)$, Output "OVERFLOW"

2. Else if $front = -1$, Set $front := 0, rear := 0$

3. Else if $front = 0$, Set $front := MAX - 1$

4. Else Set $front := front - 1$

5. Set $dq[front] := x$

InsertRear(x):

1. If $(front = 0 \text{ AND } rear = MAX-1) \text{ OR } (front = rear + 1)$, Output "OVERFLOW"

2. Else if $front = -1$, Set $front := 0, rear := 0$

3. Else if $rear = MAX - 1$, Set $rear := 0$

4. Else Set $rear := rear + 1$

5. Set $dq[rear] := x$

DeleteFront():

1. If $front = -1$, Output "UNDERFLOW"

2. Set $element := dq[front]$

3. If $front = rear$, Set $front := -1, rear := -1$

4. Else if $front = MAX - 1$, Set $front := 0$

5. Else Set $front := front + 1$

6. Return $element$

DeleteRear():

1. If $front = -1$, Output "UNDERFLOW"

2. Set $element := dq[rear]$

3. If $front = rear$, Set $front := -1, rear := -1$

4. Else if $rear = 0$, Set $rear := MAX - 1$

5. Else Set $rear := rear - 1$

6. Return $element$

Singly Linked Lists

Concept and Node Architecture

Arrays allocate memory contiguously at compile time, leading to memory space wastage if fewer elements are inserted. Linked lists allocate memory dynamically at runtime node-by-node.

• Node Anatomy: Each node contains:

  • INFO: Data payload field.

  • NEXT: Pointer containing memory address of successor node.

• Head Pointer (FIRST / START): Points to first node in list; set to NULL when list is empty.

• Tail Node: NEXT field of final node contains NULL sentinel.

C Structures and Self-Referential Declarations

To store multi-attribute data structures (e.g. Student record with roll number, name, marks):

struct student {
    int rno;          /* 4 bytes */
    char name[10];    /* 10 bytes */
    float marks;      /* 4 bytes */
};
/* Total sizeof(struct student) = 18 bytes */

A linked list node declaration uses a self-referential structure (contains a pointer to its own structure type):

struct node {
    int INFO;
    struct node *NEXT;
};

Comparison: Array vs. Linked List

Singly Linked List Operations

Traversal C Functions

/* In-order traversal */
void traverseinorder(struct node *head) {
    while(head != NULL) {
        printf("%d\n", head->INFO);
        head = head->NEXT;
    }
}

/* Reverse order traversal using recursion */
void traversereverseorder(struct node *head) {
    if(head->NEXT != NULL) {
        traversereverseorder(head->NEXT);
    }
    printf("%d\n", head->INFO);
}

Searching Functions

/* Search Unsorted Linked List */
struct node* searchunsortedlist(struct node *head, int item) {
    while((head != NULL) && (head->INFO != item)) {
        head = head->NEXT;
    }
    return head;
}

/* Search Sorted Linked List (Ascending) */
struct node* searchinsortedlist(struct node *head, int item) {
    while(head != NULL) {
        if(head->INFO == item) return head;
        else if(item < head->INFO) return NULL;
        else head = head->NEXT;
    }
    return NULL;
}

Insertion Functions

/* Insert at Beginning */
void insertatbegining(struct node **head, int item) {
    struct node *ptr = (struct node*)malloc(sizeof(struct node));
    ptr->INFO = item;
    if(*head == NULL) ptr->NEXT = NULL;
    else ptr->NEXT = *head;
    *head = ptr;
}

/* Insert at End */
void insertatend(struct node **head, int item) {
    struct node *ptr, *loc;
    ptr = (struct node*)malloc(sizeof(struct node));
    ptr->INFO = item;
    ptr->NEXT = NULL;
    if(*head == NULL) {
        *head = ptr;
    } else {
        loc = *head;
        while(loc->NEXT != NULL) loc = loc->NEXT;
        loc->NEXT = ptr;
    }
}

/* Insert After Given Element */
void insertafterelement(struct node *head, int item, int after) {
    struct node *ptr, *loc;
    loc = searchunsortedlist(head, after);
    if(loc == NULL) return;
    ptr = (struct node*)malloc(sizeof(struct node));
    ptr->INFO = item;
    ptr->NEXT = loc->NEXT;
    loc->NEXT = ptr;
}

Deletion Functions

/* Delete from Beginning */
void deletefrombegining(struct node **head) {
    struct node *ptr;
    if(*head == NULL) return;
    ptr = *head;
    *head = (*head)->NEXT;
    free(ptr);
}

/* Delete from End */
void deletefromend(struct node **head) {
    struct node *ptr, *loc;
    if(*head == NULL) return;
    if((*head)->NEXT == NULL) {
        ptr = *head;
        *head = NULL;
        free(ptr);
    } else {
        loc = *head;
        ptr = (*head)->NEXT;
        while(ptr->NEXT != NULL) {
            loc = ptr;
            ptr = ptr->NEXT;
        }
        loc->NEXT = NULL;
        free(ptr);
    }
}

/* Delete Entire List */
void deletelist(struct node **head) {
    struct node *ptr;
    while(*head != NULL) {
        ptr = *head;
        *head = (*head)->NEXT;
        free(ptr);
    }
}

Recursion and Divide-and-Conquer

Divide-and-Conquer Methodology

• Strategy: Divides a complex problem into smaller independent subproblems, solves each subproblem either directly or recursively, and recombines partial solutions into a global solution.

• Core Principle: "If the problem is too difficult to solve when it is first presented, simplify it and try again."

Mechanics of Recursion

• Definition: The mechanism where a function calls itself directly or indirectly.

• Essential Properties:

  1. Base Case: One or more simple terminating conditions that return a direct non-recursive answer.

  2. Recursive Step / General Case: Problem is redefined in terms of smaller input sizes approaching the base case.

  • Infinite Recursion Warning: Every call must strictly reduce task size; failure to reach a base case causes call stack overflow.

• Direct Recursion: Function $A$ explicitly invokes $A$.

• Indirect Recursion: Function $A$ calls $B$, and $B$ subsequently calls $A$.

Iteration vs. Recursion

Recursion Examples

Sum of First $n$ Positive Integers

/* Recursive sum implementation */
int sum(int n) {
    if (n <= 1) return n;            /* Base case */
    else return (n + sum(n - 1));    /* General recursive step */
}

Trace for sum(5):

$\text{sum}(5) \rightarrow 5 + \text{sum}(4) \rightarrow 5 + (4 + \text{sum}(3)) \rightarrow 5 + 4 + (3 + \text{sum}(2)) \rightarrow 5 + 4 + 3 + (2 + \text{sum}(1)) \rightarrow 5 + 4 + 3 + 2 + 1 = 15$

Factorial Function ($n!$)

Mathematical definition: $n! = n \times (n-1)!$ where $0! = 1! = 1$.

#include <stdio.h>

long factorial(long number) {
    if (number <= 1) return 1;                    /* Base case */
    else return (number * factorial(number - 1));  /* Recursive step */
}

int main() {
    int i;
    for (i = 1; i <= 10; i++) {
        printf("%2d! = %ld\n", i, factorial(i));
    }
    return 0;
}

Fibonacci Series

Definition: $fib(n) = fib(n-1) + fib(n-2)$ where $fib(0) = 0, fib(1) = 1$.

long fibonacci(long n) {
    if (n == 0 || n == 1) return n;  /* Base case */
    else return fibonacci(n - 1) + fibonacci(n - 2);  /* Double recursion */
}

• Complexity: Time complexity is exponential $O(2^n)$ due to redundant sub-tree recalculations.

Towers of Hanoi

• Puzzle Rules: Move $N$ disks from peg BEG to peg END using auxiliary peg AUX.

  1. Move only 1 disk at a time.

  2. Only top disk can be moved.

  3. No larger disk may be placed on a smaller disk.

Algorithm TOWER(N, BEG, AUX, END):

1. If $N = 1$, then:

   • Write: $BEG \rightarrow END$

   • Return

2. Call TOWER(N - 1, BEG, END, AUX)

3. Write: $BEG \rightarrow END$

4. Call TOWER(N - 1, AUX, BEG, END)

5. Return

Algorithm Analysis and Asymptotic Notations

Principles of Asymptotic Analysis

Asymptotic analysis measures algorithm efficiency as input size $n \to \infty$, evaluating runtime or space requirements independently of hardware, compiler, or programming language.

Types of Analysis

• Worst-Case Analysis (Upper Bound): Calculates maximum execution operations for input of size $n$. (Standard benchmark; e.g. linear search when item is absent requires $n$ comparisons).

• Best-Case Analysis (Lower Bound): Calculates minimum operations required. (e.g. linear search when item is at index $0$ requires $O(1)$ comparisons).

• Average-Case Analysis: Calculates expected computing time across all uniformly distributed input cases.

Asymptotic Notations

Big-O Notation (Upper Bound / Worst Case)

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

$f(n) \le c \cdot g(n) \quad \forall n \ge n_0$

Mathematical Proof Example:

Prove $f(n) = 2n + 3 = O(n)$.

Condition: $2n + 3 \le c \cdot n$

Let $c = 5$ and $n_0 = 1$:

• For $n = 1$: $2(1) + 3 = 5 \le 5(1)$ (True)

• For $n = 2$: $2(2) + 3 = 7 \le 5(2) = 10$ (True)

Thus, $f(n) = O(n)$.

Big-Omega Notation (Lower Bound / Best Case)

$f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

$f(n) \ge c \cdot g(n) \quad \forall n \ge n_0$

Mathematical Proof Example:

Prove $f(n) = 2n + 3 = \Omega(n)$.

Condition: $2n + 3 \ge c \cdot n$

Choose $c = 1, n_0 = 1$:

$2n + 3 \ge 1 \cdot n \quad \forall n \ge 1 \quad \text{(True)}$

Big-Theta Notation (Tight Bound / Average Case)

$f(n) = \Theta(g(n))$ if there exist positive constants $c_1, c_2$, and $n_0$ such that:

$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \forall n \ge n_0$

Mathematical Proof Example:

Prove $f(n) = 2n + 8 = \Theta(n)$.

Condition: $c_1 \cdot n \le 2n + 8 \le c_2 \cdot n$

Let $c_1 = 2, c_2 = 6, n_0 = 2$:

$2(2) \le 2(2) + 8 \le 6(2) \implies 4 \le 12 \le 12 \quad \text{(True)}$

Rate of Growth Comparison

Standard complexity ordering:

$O(1) < O(\log(n)) < O(n) < O(n \log(n)) < O(n^2) < O(n^3) < O(2^n)$

Function Values Growth Comparison Table

Common Time Complexities Summary