Complexity analysis is essential for competitive engineering exams because it measures scalability, not just correctness. PSC questions commonly ask ADT definition, Big O/Theta/Omega, loop counting, recurrence intuition and best/average/worst-case difference.
Engineering Definitions
ADT
Standard definition: A logical specification of data values and operations independent of implementation.
Exam meaning: Implementation भन्दा बाहिर operation behavior define गर्ने abstract model।
Time complexity
Standard definition: A function describing how running time grows with input size.
Exam meaning: Input size बढ्दा algorithm को समय कसरी बढ्छ भन्ने analysis।
Space complexity
Standard definition: A function describing how memory usage grows with input size.
Exam meaning: Input size बढ्दा memory usage कसरी बढ्छ भन्ने analysis।
Big O
Standard definition: An asymptotic upper bound on growth rate.
Exam meaning: Worst-side upper growth limit बताउने notation।
Theta
Standard definition: A tight asymptotic bound from both above and below.
Exam meaning: Exact growth class बताउने tight bound।
Concept Teaching
Algorithm analysis ignores machine-specific constants and focuses on growth. A program that is fast for 100 inputs can fail for one million inputs if complexity grows poorly. ADT separates what operations mean from how arrays, lists, trees or heaps implement them.
ADT vs Data Structure
This distinction is a classic theory-to-practice point.
| Item | Meaning | Example |
|---|---|---|
| ADT | Logical behavior and operations | Stack: push, pop, top |
| Data structure | Concrete memory organization | Array stack or linked-list stack |
| Implementation | Code realization | C/C++/Java/Python class |
Asymptotic Notation
Notation compares growth for large input size.
| Notation | Meaning | Typical phrase |
|---|---|---|
| O(g(n)) | Upper bound | No faster than this growth asymptotically |
| Omega(g(n)) | Lower bound | At least this growth |
| Theta(g(n)) | Tight bound | Same growth order |
Loop Counting
Most MCQs come from loops.
- Single loop to n is O(n).
- Nested independent loops to n are O(n^2).
- Loop doubling i = i*2 is O(log n).
- Sequential blocks add; keep dominant term.
- Nested loops multiply; consecutive loops add.
- Drop constants and lower-order terms.
Case Analysis
Best, average and worst case describe input-dependent behavior.
- Best case is minimum time among inputs of size n.
- Worst case is maximum time among inputs of size n.
- Average case requires probability distribution over inputs.
- Linear search best case O(1), worst case O(n).
- Binary search requires sorted data and is O(log n).
Engineering Mechanism
- Define input size n.
- Identify primitive operation to count.
- Derive count from loops/recursion/branches.
- Keep dominant growth term.
- Classify with O, Omega or Theta.
- State assumptions such as sorted input or balanced tree.
Diagrams / Models To Draw
- Draw growth-rate chart: log n, n, n log n, n^2, 2^n.
- Draw ADT vs implementation mapping.
- Draw recursion tree for divide and conquer.
- Draw loop nesting count grid.
Formulas, Algorithms and Code Patterns
- Arithmetic series: 1+2+…+n = n(n+1)/2 = Theta(n^2).
- Binary search recurrence T(n)=T(n/2)+O(1)=O(log n).
- Merge sort recurrence T(n)=2T(n/2)+O(n)=O(n log n).
- Drop constants: O(3n+10)=O(n).
| Growth | Example | Scalability |
|---|---|---|
| O(1) | Array index access | Excellent |
| O(log n) | Binary search | Very good |
| O(n) | Linear scan | Acceptable |
| O(n log n) | Merge sort | Good for sorting |
| O(n^2) | Simple nested comparison | Poor for large n |
| O(2^n) | Brute-force subsets | Explosive |
Exam Point
- Mention assumptions in complexity answers.
- Theta is tighter than Big O.
- Average case is not guesswork; it needs input distribution.
- Binary search needs sorted data.
- ADT is specification, data structure is implementation.
Worked Example
For `for i=1..n: for j=1..i: x++`, inner loop runs 1+2+…+n times = n(n+1)/2, so time is Theta(n^2). The exact count has lower terms, but asymptotic growth is quadratic.
Subjective Answer Pattern
- Define ADT and complexity.
- Explain asymptotic notation.
- Show loop/recurrence counting method.
- Discuss best/average/worst case.
- Give examples of common growth rates.
Common Engineering Mistakes
- Calling Big O exact time.
- Ignoring nested loop dependency.
- Saying binary search works on unsorted array.
- Confusing ADT with class implementation.
- Using average case without probability assumption.
MCQ Revision
- What is Big O?
- What is Theta?
- Complexity of binary search?
- Complexity of two nested n loops?
- Is stack an ADT or implementation?
- What is linear search worst case?
Final Summary
- ADT defines behavior independent of implementation.
- Complexity measures growth with input size.
- Big O is upper bound; Theta is tight bound.
- Loop and recurrence analysis are core exam skills.
- Case analysis depends on input behavior.