Evaluating Postfix Expression: 5 7 4 - * 8 / 4 +

Given Data

• Postfix expression: 5 7 4 - * 8 / 4 +
• Data structure to use: Stack

Algorithm (Postfix Evaluation)

1. Scan the expression left to right.
2. If the symbol is an operand, push it onto the stack.
3. If the symbol is an operator, pop the top two operands:
   • op2 = first pop (right operand)
   • op1 = second pop (left operand)
   • Compute op1 <operator> op2 and push the result.
4. The final remaining stack element is the result.

Step-by-Step Trace

Handling the Division at Step 7

The value $15 / 8 = 1.875$.

Case A: Integer division (common in textbook/C-style examples): $$15 / 8 = 1$$ Then:

• Step 8: Push 4 → stack: 1, 4
• Step 9: $1 + 4 = 5$

Final result = 5

Case B: Real (floating-point) division: $$15 / 8 = 1.875$$ Then:

• Step 8: Push 4 → stack: 1.875, 4
• Step 9: $1.875 + 4 = 5.875$

Final result = 5.875

Result

Since this is a data structures problem typically evaluated with integer arithmetic, the standard exam answer is:

$$\boxed{5\ 7\ 4\ -\ *\ 8\ /\ 4\ +\ =\ 5}$$

(If real-number division is intended, the result would be $5.875$.)

The trace gives a final value of 5 (using integer division).

Asymptotic Notation and Big Oh Notation

Why Do We Need Asymptotic Notation? (2 marks)

When we analyze algorithms, we need a way to measure and compare their efficiency (time and space) without depending on machine speed, programming language, or hardware. Asymptotic notation provides a mathematical framework to describe the behavior of an algorithm as the input size grows toward infinity.

Key reasons we need asymptotic notation:

• To compare two algorithms independently of machine or implementation details.
• To describe the growth rate of an algorithm's running time or space requirement.
• To focus on the dominant term of a function and ignore constants and lower-order terms, which become insignificant for large inputs.
• To express best case, worst case, and average case complexity in a standard, concise way.

For example, if an algorithm takes T(n) = 5n² + 3n + 10 steps, asymptotic notation lets us simply say it grows as n², ignoring less significant terms.

Big Oh Notation O(g(n)) (3 marks)

Definition:

"When we have only asymptotic upper bound then we use O notation. If f and g are any two functions from set of integers then function f(x) is said to be big Oh of g(x)."

Formally:

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

$$f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$$

• f(n) is the actual running time of the algorithm.
• g(n) is the bounding function (upper bound).
• c and n₀ are positive constants.

This means Big Oh gives the worst-case or upper bound on the growth of an algorithm.

Example

If f(n) = 4n + 2, then:

• 4n + 2 ≤ 5n for all n ≥ 2
• So f(n) = O(n), with c = 5 and n₀ = 2

Curve / Graphical Representation

  Running
  Time
    |                         c * g(n)
    |                      ./
    |                   ./
    |               .../  <-- f(n) always stays
    |           .../        below c*g(n) after n₀
    |       .../
    |   .../
    |../
    |_________________________ n
              n₀

• For all values of n ≥ n₀, the curve of f(n) lies at or below the curve of c * g(n).
• Big Oh notation thus represents the asymptotic upper bound.

Key Points

Common Big Oh Complexities (Best to Worst)

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

Conclusion: Big Oh notation is the most widely used asymptotic notation because it tells us the maximum time an algorithm will ever take, helping us guarantee performance in the worst case.