Big Theta Notation and Stack Applications in C++

Midterm Activity
April 7, 2026

Course: Data Structures

Language: C++
Subject: Big Theta Notation and Stack Operations

TASKS

Task 1 — Linear Loop (Θ(n))

Question:
What is the time complexity of a single loop?
Answer:
The time complexity of a single loop that iterates from 1 to n is Θ(n) — linear time. This means the
number of operations grows directly proportional to the input size n. If n doubles, the number of
iterations (and thus the execution time) also doubles. A single loop performs exactly n iterations, so it
scales linearly.

C++ Program:
#include <iostream> // Include the standard I/O library for cout
using namespace std; // Use standard namespace so we don't need std:: prefix

int main() {
int n = 10; // Define the upper limit; this controls how many times the loop runs

// Single for-loop: runs exactly n times → time complexity is Θ(n)

// Each iteration performs one print operation (constant work O(1))
// Total work = n × O(1) = Θ(n) — grows linearly with n
for (int i = 1; i <= n; i++) {
cout << i << " "; // Print the current number followed by a space
}

cout << endl; // Move to the next line after printing all numbers
return 0; // Return 0 to indicate successful program termination
}

// COMPLEXITY ANALYSIS:
// - The loop starts at i=1 and stops when i > n
// - Total iterations = n (one for each number from 1 to n)
// - Each iteration does O(1) work (just printing)
// - Overall: Θ(n) — if n=10 → 10 ops; if n=100 → 100 ops (scales linearly)

Expected Output (n=10):

1 2 3 4 5 6 7 8 9 10
Task 2 — Nested Loop (Θ(n²))
Question:
Why do nested loops increase complexity?
Answer:
Nested loops multiply complexities. When an outer loop runs n times and for each of those n iterations
an inner loop also runs n times, the total number of operations becomes n × n = n². This quadratic
growth means that if n doubles, the work quadruples. Each additional level of nesting multiplies the
complexity by another factor of n.

C++ Program:
#include <iostream> // Include I/O library for cout
using namespace std; // Use standard namespace

int main() {
int n = 5; // Size of the square pattern (n×n grid)

// Outer loop: runs n times (one per row)

// Controls the ROW dimension → iterates n times
for (int i = 1; i <= n; i++) {

// Inner loop: runs n times FOR EACH outer iteration

// Controls the COLUMN dimension → also iterates n times
// Total iterations = n (outer) × n (inner) = n²
// This is why nested loops yield Θ(n²) complexity
for (int j = 1; j <= n; j++) {
cout << "* "; // Print a star for each column position
}

cout << endl; // After each full row, move to the next line
}

return 0; // Program ends successfully

}

// COMPLEXITY ANALYSIS:
// - Outer loop runs n times
// - Inner loop runs n times for each outer iteration
// - Total print operations = n × n = n²
// - If n=5 → 25 operations
// - If n=10 → 100 operations (4× more work for 2× input)
// - This multiplication of loops is why complexity is Θ(n²)

Expected Output (n=5):

* * * * *
* * * * *
* * * * *
* * * * *
* * * * *

Task 3 — Logarithmic Loop (Θ(log n))

Question:
Why is doubling (i *= 2) considered logarithmic?
Answer:
When i doubles each iteration (i *= 2), the loop reaches n in log₂(n) steps instead of n steps. This is
because doubling is the inverse of the logarithm — the number of times you can multiply 1 by 2 before
reaching n is exactly log₂(n). For example, if n=1024, the loop runs only 10 times (2^10 = 1024), not
1024 times. As n grows, the number of iterations grows much more slowly — that slow growth is the
hallmark of logarithmic complexity.

C++ Program:
#include <iostream> // Include I/O library for cout
using namespace std; // Use standard namespace

int main() {
int n = 64; // Upper limit; the loop will stop when i exceeds n
int count = 0; // Counter to track how many iterations actually run

// Logarithmic loop: i doubles every iteration (i *= 2)

// i starts at 1 and becomes: 1, 2, 4, 8, 16, 32, 64 → stops at 128 > 64
// Total iterations = log₂(n) = log₂(64) = 6
// REASON: Doubling reduces the 'distance' to n exponentially each step
// so fewer iterations are needed compared to i++ (linear)
for (int i = 1; i <= n; i *= 2) {
count++; // Increment iteration counter
cout << "i = " << i // Show current value of i
<< " (iteration #" << count << ")" << endl;
}

// Display how many times the loop actually ran

// This proves the loop ran log₂(n) times, not n times
cout << "Total iterations: " << count << endl;
cout << "Expected log2(" << n << ") = " << 6 << endl;

return 0; // Program ends successfully

}

// COMPLEXITY ANALYSIS:
// - i sequence: 1 → 2 → 4 → 8 → 16 → 32 → 64 → (128 > 64, stops)
// - Number of steps = log₂(64) = 6
// - Compare: a linear loop (i++) would need 64 iterations for n=64
// - Θ(log n) is far more efficient than Θ(n) for large n

Expected Output (n=64):

i = 1 (iteration #1)
i = 2 (iteration #2)
i = 4 (iteration #3)
i = 8 (iteration #4)
i = 16 (iteration #5)
i = 32 (iteration #6)
i = 64 (iteration #7)
Total iterations: 7
Expected log2(64) = 6

Task 4 — Combined Complexity (Θ(n log n))

Question:
What happens when you combine logarithmic and linear loops?
Answer:
When a logarithmic outer loop (log n iterations) contains a linear inner loop (n iterations each), the
complexities multiply: log n × n = n log n. This is the complexity of efficient sorting algorithms like Merge
Sort and Quick Sort. It grows faster than Θ(n) but much slower than Θ(n²), making it an excellent
balance of efficiency for large datasets.

C++ Program:
#include <iostream> // Include I/O library for cout
using namespace std; // Use standard namespace

int main() {
int n = 8; // Input size
int opCount = 0; // Count total inner operations to verify n log n

// OUTER LOOP: Logarithmic — doubles each time → runs log₂(n) times

// For n=8: outer runs log₂(8) = 3 times (i = 1, 2, 4)
for (int i = 1; i <= n; i *= 2) {

// INNER LOOP: Linear — runs n times for EVERY outer iteration

// This is the 'n' factor that combines with the outer 'log n'
for (int j = 1; j <= n; j++) {
opCount++; // Count this operation
// Print outer (i) and inner (j) loop values
cout << "(i=" << i << ", j=" << j << ") ";
}
cout << endl; // New line after each outer iteration
}

// Show total operations — should approximate n * log2(n)

cout << "Total operations: " << opCount << endl;
cout << "n * log2(n) = " << n << " * 3 = " << (n * 3) << endl;

return 0;
}

// FINAL COMPLEXITY ANALYSIS:

// - Outer loop (i *= 2) runs: log₂(n) times
// - Inner loop (j++) runs: n times per outer iteration
// - Total operations = log₂(n) × n = n log n
// - For n=8: 3 outer × 8 inner = 24 operations
// - n log₂ n = 8 × 3 = 24 ✓ (matches!)
// - Θ(n log n) is the sweet spot: better than Θ(n²), used in sorting algorithms

Expected Output (n=8):

(i=1, j=1) (i=1, j=2) ... (i=1, j=8)
(i=2, j=1) (i=2, j=2) ... (i=2, j=8)
(i=4, j=1) (i=4, j=2) ... (i=4, j=8)
Total operations: 24
n * log2(n) = 8 * 3 = 24

Task 5 — Stack Basics

Question:
What is a stack and how does LIFO work?
Answer:
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the last element
added is the first one removed, just like a stack of plates. You can only interact with the top element. In
C++, the STL provides a built-in stack<T> container. LIFO means: if you push 10, then 20, then 30, the
top is 30. Popping removes 30 first, then 20, then 10 — the reverse of insertion order.

C++ Program:
#include <iostream> // Required for cout (console output)
#include <stack> // Required for the stack<T> STL container
using namespace std; // Use standard namespace to avoid std:: prefix

int main() {
stack<int> s; // Declare an integer stack; initially empty

// PUSH operation: adds an element to the TOP of the stack

// LIFO order means 30 will be on top (it was pushed last)
[Link](10); // Stack from bottom to top: [10]
[Link](20); // Stack from bottom to top: [10, 20]
[Link](30); // Stack from bottom to top: [10, 20, 30] ← 30 is on top

// Display what's on top — should be 30 (last pushed = first to be popped)

// This demonstrates LIFO: Last In = 30, so it's First Out
cout << "Top element: " << [Link]() << endl;

// Display the current size of the stack

cout << "Stack size: " << [Link]() << endl;

return 0; // End of program

}

// STACK ORDER EXPLANATION:

// Push 10 → stack: [10]
// Push 20 → stack: [10, 20]
// Push 30 → stack: [10, 20, 30]
// top() → returns 30 (last in, first out = LIFO)
// Popping would remove: 30, then 20, then 10 (reverse insertion order)

Expected Output:
Top element: 30
Stack size: 3

Task 6 — Stack Operations

Question:
What do push(), pop(), and top() do?
Answer:
push(val) adds a value to the top of the stack. top() returns (but does not remove) the current top
element. pop() removes the top element without returning it — you must call top() first if you need the
value. These three operations form the core interface of a stack and all run in O(1) constant time.

C++ Program:
#include <iostream> // For cout
#include <stack> // For stack<T>
using namespace std;

int main() {
stack<int> s; // Declare an empty integer stack
 // push(): Adds element to the TOP of the stack — O(1) operation
[Link](100); // Stack: [100]
[Link](200); // Stack: [100, 200]
[Link](300); // Stack: [100, 200, 300] ← 300 is now on top

// top(): Returns the top element WITHOUT removing it

// Use this to PEEK at the top before deciding to pop
cout << "Current top (before pop): " << [Link]() << endl; // Prints 300

// pop(): REMOVES the top element (does NOT return it)

// Always call top() first if you need the value
[Link](); // Removes 300 → Stack is now: [100, 200]

// top() again — now shows 200 (the new top after removing 300)
cout << "Current top (after pop): " << [Link]() << endl; // Prints 200

// Show updated size

cout << "Stack size after pop: " << [Link]() << endl; // Was 3, now 2

return 0;
}

// push(x) → adds x on top | O(1)

// top() → reads top value | O(1) — does NOT remove
// pop() → removes top | O(1) — does NOT return the value

Expected Output:
Current top (before pop): 300
Current top (after pop): 200
Stack size after pop: 2

Task 7 — Empty and Size Check

Question:
Why is it important to check empty()?
Answer:
Calling top() or pop() on an empty stack causes undefined behavior (a crash or garbage value) in C++.
The empty() function returns true when the stack has no elements, allowing safe guards before
accessing or removing elements. Always check empty() before calling top() or pop() to prevent runtime
errors. size() returns the number of elements currently in the stack.

C++ Program:
#include <iostream> // For cout
#include <stack> // For stack<T>
using namespace std;

int main() {
stack<int> s; // Declare an empty integer stack

// Push several values onto the stack

[Link](5); // Stack: [5]
[Link](10); // Stack: [5, 10]
[Link](15); // Stack: [5, 10, 15]

cout << "Size before removal: " << [Link]() << endl; // Output: 3
 // Remove ALL elements using pop() inside a loop
// Check empty() before each pop to safely drain the stack
// Without empty() check: popping an empty stack causes undefined behavior!
while (![Link]()) { // Loop continues as long as stack is NOT empty
cout << "Popping: " << [Link]() << endl; // Show value before removing it
[Link](); // Remove the top element
}

// After the loop, all elements have been removed

// Now check if the stack is empty — it should be
if ([Link]()) {
cout << "Stack is now empty!" << endl; // Confirms all elements removed
} else {
cout << "Stack still has elements." << endl;
}

// Display size — should be 0 after clearing

cout << "Size after removal: " << [Link]() << endl; // Output: 0

return 0;
}

// WHY empty() MATTERS:

// [Link]() on empty stack → undefined behavior (crash/garbage)
// [Link]() on empty stack → undefined behavior (crash)
// empty() returns true when size == 0, preventing these errors

Expected Output:
Size before removal: 3
Popping: 15
Popping: 10
Popping: 5
Stack is now empty!
Size after removal: 0

Task 8 — Function Call Stack

Question:
How does stack apply in function calls?
Answer:
Every time a function is called, the CPU pushes a 'stack frame' onto the call stack — this frame stores
local variables, parameters, and the return address. When the function finishes, its frame is popped and
execution returns to the caller. This is exactly LIFO behavior: the last function called is the first to finish
and return. Deeply nested function calls increase stack depth; unbounded recursion causes a 'stack
overflow'.

C++ Program:
#include <iostream> // For cout
using namespace std;

// functionB is declared first so functionA can call it

// When functionB is called, its stack frame is pushed ON TOP of functionA's frame
void functionB() {
// At this point, the call stack looks like:
// [main] ← bottom
 // [functionA] ← pushed when main called functionA
// [functionB] ← pushed when functionA called functionB (currently executing)
cout << " [functionB] Executing — deepest call, top of the call stack" << endl;
// functionB finishes → its stack frame is POPPED
// Execution returns to functionA (the frame below it)
}

// functionA is the middle layer — it calls functionB

void functionA() {
// At this point, the call stack is: [main] → [functionA]
cout << "[functionA] Starting — calling functionB now..." << endl;

functionB(); // Push functionB's frame onto the stack; execute it; then pop

// After functionB returns, execution resumes here

// The call stack is back to: [main] → [functionA]
cout << "[functionA] Resumed after functionB returned" << endl;
// functionA finishes → its stack frame is POPPED → returns to main
}

int main() {
// Call stack starts with just [main]
cout << "[main] Starting — calling functionA..." << endl;

functionA(); // Push functionA's stack frame; this also triggers functionB

// After functionA (and functionB inside it) return, we're back in main
cout << "[main] Resumed after functionA returned" << endl;

return 0;
}

// EXECUTION ORDER (LIFO — stack-based):

// 1. main() starts
// 2. functionA() is called (pushed)
// 3. functionB() is called (pushed)
// 4. functionB() finishes (popped) → returns to functionA
// 5. functionA() finishes (popped) → returns to main
// 6. main() finishes (popped) → program ends

Expected Output:
[main] Starting — calling functionA...
[functionA] Starting — calling functionB now...
[functionB] Executing — deepest call, top of the call stack
[functionA] Resumed after functionB returned
[main] Resumed after functionA returned

Task 9 — Stack Application (Balanced Parentheses)

Question:
How does stack help in checking balanced symbols?
Answer:
A stack is ideal for balanced-symbol checking because opening brackets need to be matched with their
corresponding closing brackets in reverse order — which is exactly LIFO behavior. When an opening
bracket is encountered, push it. When a closing bracket is encountered, check if the top of the stack is
its matching opener — if yes, pop it; if no, the string is unbalanced. After processing all characters, if
the stack is empty, the string is balanced.
C++ Program:
#include <iostream> // For cout
#include <stack> // For stack<char>
#include <string> // For string type
using namespace std;

// Function that checks if a string of brackets is balanced

// Returns true if balanced, false otherwise
bool isBalanced(string expr) {
stack<char> s; // Stack stores unmatched opening brackets

// Process each character in the expression one by one

for (int i = 0; i < [Link](); i++) {
char ch = expr[i]; // Get the current character

// If it's an OPENING bracket, push it onto the stack

// We store it so we can match it later with its closing counterpart
if (ch == '(' || ch == '[' || ch == '{') {
[Link](ch); // Push opening bracket — waiting for its match
cout << " Push: '" << ch << "' | Stack size: " << [Link]() << endl;
}

// If it's a CLOSING bracket, it must match the top of the stack

else if (ch == ')' || ch == ']' || ch == '}') {

// If stack is empty, there's no matching opener → unbalanced

if ([Link]()) {
cout << " Unmatched closing bracket: '" << ch << "'" << endl;
return false;
}

char top = [Link](); // Peek at the most recent unmatched opener

// Check if the closing bracket correctly matches the top opener

// '(' must be closed by ')', '[' by ']', '{' by '}'
bool matched = (ch == ')' && top == '(') ||
(ch == ']' && top == '[') ||
(ch == '}' && top == '{');

if (matched) {
[Link](); // Pop the matched opener from the stack
cout << " Pop: '" << top << "' matched by '" << ch
<< "' | Stack size: " << [Link]() << endl;
} else {
// Closing bracket doesn't match the opener on top → unbalanced
cout << " Mismatch: '" << top << "' vs '" << ch << "'" << endl;
return false;
}
}
}

// If stack is empty, all openers have been matched and popped → balanced
// If stack is NOT empty, some openers were never closed → unbalanced
return [Link]();
}

int main() {
string expr = "{[()]}"; // The expression to check

cout << "Checking: " << expr << endl;

 if (isBalanced(expr)) {
cout << "Result: BALANCED" << endl; // All brackets matched correctly
} else {
cout << "Result: NOT BALANCED" << endl;
}

return 0;
}

// TRACE FOR {[()]}:

// '{' → push → stack: ['{']
// '[' → push → stack: ['{', '[']
// '(' → push → stack: ['{', '[', '(']
// ')' → top is '(' → match! pop → stack: ['{', '[']
// ']' → top is '[' → match! pop → stack: ['{']
// '}' → top is '{' → match! pop → stack: []
// Stack is empty → BALANCED ✓

Expected Output:
Checking: {[()]}
Push: '{' | Stack size: 1
Push: '[' | Stack size: 2
Push: '(' | Stack size: 3
Pop: '(' matched by ')' | Stack size: 2
Pop: '[' matched by ']' | Stack size: 1
Pop: '{' matched by '}' | Stack size: 0
Result: BALANCED

Task 10 — Mini Application (Menu Program)

Question:
Why is a menu-driven stack useful?
Answer:
A menu-driven stack program provides an interactive interface that lets users control stack operations
step by step — pushing specific values, popping elements, viewing the top, and checking if the stack is
empty. This is useful because it mirrors how real-world applications (like undo systems, browser
history, or expression evaluators) expose stack functionality to users without exposing the underlying
data structure. It also allows testing and verifying stack behavior at runtime.

C++ Program:
#include <iostream> // For cout and cin
#include <stack> // For stack<int>
using namespace std;

// Display the menu of available operations to the user

void showMenu() {
cout << "\n====== STACK MENU ======" << endl;
cout << "1. Push (add element)" << endl; // Adds element to top
cout << "2. Pop (remove top) " << endl; // Removes top element
cout << "3. Top (view top) " << endl; // Peeks at top without removing
cout << "4. Empty (check if empty)" << endl; // Checks if stack has elements
cout << "5. Exit" << endl;
cout << "========================" << endl;
cout << "Choose an option: ";
}

int main() {
 stack<int> s; // Declare the main stack — starts empty
int choice; // Stores the user's menu selection
int value; // Stores the value to push (used in case 1)

// Main program loop — keeps showing menu until user selects Exit
do {
showMenu(); // Display the operation menu
cin >> choice; // Read user's choice

switch (choice) {

case 1: // PUSH — add a value to the top of the stack

cout << "Enter value to push: ";
cin >> value; // Get the value from the user
[Link](value); // Push it onto the stack
cout << value << " pushed onto the stack." << endl;
cout << "Stack size is now: " << [Link]() << endl;
break;

case 2: // POP — remove the top element

if ([Link]()) {
// Guard: must check empty before pop to avoid undefined behavior
cout << "Cannot pop — stack is empty!" << endl;
} else {
cout << [Link]() << " popped from the stack." << endl;
[Link](); // Remove the top element
cout << "Stack size is now: " << [Link]() << endl;
}
break;

case 3: // TOP — view the top element without removing it

if ([Link]()) {
// Guard: top() on empty stack is undefined behavior
cout << "Stack is empty — no top element." << endl;
} else {
cout << "Top element: " << [Link]() << endl; // Peek at top
}
break;

case 4: // EMPTY — check if stack has no elements

if ([Link]()) {
cout << "Stack is EMPTY (size = 0)." << endl;
} else {
cout << "Stack is NOT empty. Size: " << [Link]() << endl;
}
break;

case 5: // EXIT — terminate the menu loop

cout << "Exiting program. Goodbye!" << endl;
break;

default: // Invalid choice — prompt user to try again

cout << "Invalid option. Please choose 1-5." << endl;
}

} while (choice != 5); // Keep looping until user selects Exit (5)

return 0;
}

// SAMPLE RUN (3+ operations demonstrated):

// Choose: 1 → Enter: 42 → '42 pushed' (Push)
// Choose: 1 → Enter: 99 → '99 pushed' (Push)
// Choose: 3 → → 'Top: 99' (Top)
 // Choose: 4 → → 'Not empty, size: 2' (Empty check)
// Choose: 2 → → '99 popped' (Pop)
// Choose: 5 → → 'Goodbye!' (Exit)

Sample Output (3+ operations):

====== STACK MENU ======
1. Push (add element)
2. Pop (remove top)
3. Top (view top)
4. Empty (check if empty)
5. Exit
========================
Choose an option: 1
Enter value to push: 42
42 pushed onto the stack.
Stack size is now: 1

Choose an option: 1
Enter value to push: 99
99 pushed onto the stack.
Stack size is now: 2

Choose an option: 3
Top element: 99

Choose an option: 4
Stack is NOT empty. Size: 2

Choose an option: 2
99 popped from the stack.
Stack size is now: 1

Choose an option: 5
Exiting program. Goodbye!