Algorithm Efficiency and Summation Reference

Analyzing Algorithm Efficiency

Exponential Recursive Calls

return f(n-1) + f(n-1)

❌ Very bad algorithm
Why: It results in an exponential number of calls and massive recomputation.
Better: Use iterative multiplication or fast exponentiation.

Recursive vs. Iterative Practice

S(n) = S(n-1) + n*n*n

⚠️ Same asymptotic cost as iterative, but worse in practice
Why: Recursion adds significant stack overhead.
Better: Use a loop or a closed-form formula.

Efficient Linear Algorithms

return Q(n-1) + 2*n - 1

✅ Efficient linear algorithm

Multiplications: Θ(n), Additions: Θ(n).
Why: There is no redundant computation.

Optimal Element Inspection

temp = recursive call
if temp <= A[n-1]

✅ Optimal
Why: You must look at every element; therefore, Θ(n) is unavoidable.

Improving Summation Performance

for i = 1 to n:
  S += i*i

Last question answer (Improvement):
✅ Use formula → Θ(1)

n(n+1)(2n+1)/6

Optimizing Min-Max Comparisons

if A[i] < min
if A[i] > max

Last question answer (Improvement):
⚡ Compare elements in pairs
Why: Reduces comparisons from approximately 2n to 1.5n.
Class: Still Θ(n), but faster in practice.

Matrix Symmetry Lower Bounds

if A[i][j] != A[j][i]

❌ No improvement possible.
Why: You must check approximately n²/2 elements, leading to a Θ(n²) lower bound.

Common Summation Formulas and Orders