Introduction – Algorithm Specification, Pseudo code for expressing algorithms, Performance Analysis-Space complexity, Time
complexity, Asymptotic NotationBig oh notation, Omega notation, Theta notation and Little oh notation, Performance Measurement,
Randomized algorithms.
Algorithm:
• An algorithm is a finite sequence of unambiguous(clear) instructions that, given valid inputs, produces correct outputs and
terminates in a finite amount of time
Key Characteristics of Algorithm
These five properties are essential and widely acknowledged
1. Input
The algorithm must accept zero or more inputs, taken before or during execution.
2. Output
It must produce at least one output, the result of the computation.
3. Definiteness
Each step should be clear and unambiguous, with no confusion about what to do.
4. Finiteness
It must terminate after a finite number of steps—it can’t go on forever.
5. Effectiveness
All operations should be basic enough to be performed by hand or simple code.
Algorithm specification
• Algorithm specification is the process of clearly and precisely describing an algorithm — what it does, how it works, and
how it should be executed. It includes the steps, inputs, expected outputs, and rules that define the algorithm.
A Good Algorithm Specification Should:
• Define the problem clearly
• Mention the input
• List the steps clearly
• Mention the output
• Keep it easy to understand
How to Write an Algorithm
Algorithms can be expressed in several ways:
• Plain English
Useful for informal explanations or conceptual walkthroughs.
• Flowcharts
Visual mapping using decision symbols and arrows—great for illustrating logic flow
• Pseudocode
A structured, language-agnostic format that closely mirrors code syntax and control structures. It is clearer than prose but
doesn't require exact syntax of a programming language.
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 – STOP
Pseudo code for expressing algorithms
Pseudocode is a high-level, language-independent way of describing an algorithm.. It bridges the gap between natural language and
programming code.
Characteristics od pseudo code:
1. Language-neutral – It’s not written in any specific programming language.
2. Structured – Uses standard control structures like:
o IF, THEN, ELSE
o WHILE, FOR, REPEAT-UNTIL
o PROCEDURE, FUNCTION, RETURN
3. Clarity & Precision – Each step is clearly defined.
4. No Syntax Rules – Unlike real programming languages, no strict syntax or punctuation is required.
Pseudo code for linear search :
START
Input array and size
Input element to search (X)
Set found = false
For each element in array
If element = X
Print "Found"
Set found = true
Break
End If
End For
If found = false
Print "Not found"
End If
STOP
Performance analysis:
Performance analysis is the process of evaluating an algorithm based on the time and memory it uses.
It helps determine the algorithm's efficiency in solving a problem.
• Space Complexity
Space complexity measures how much memory an algorithm needs to execute, as a function of the input size n.
It includes:
1. Input space – Memory used to store the input.
2. Auxiliary space – Temporary or working variables (e.g., loops, counters).
3. Function call space – Used during recursion (stack frames,functions).
4. Output space – If the algorithm generates and stores results.
Types of Space complexity:
• Constant Space – O(1):
Uses a fixed amount of memory regardless of input size.
Example: Swapping two variables, using a single counter.
• Linear Space – O(n):
Memory grows linearly with input.
Example: Storing an input array, copying data.
• Logarithmic Space – O(log n):
Used in divide-and-conquer algorithms (e.g., binary search).
• Quadratic or Higher – O(n²), O(n³):
Seen in matrix algorithms or nested loops.
Time Complexity
Time complexity measures how much time an algorithm needs to execute, as a function of the input size n. It doesn't track clock
time but counts the number of basic operations (e.g., comparisons, assignments).
Types of Time Complexity:
Notation Meaning
O(1) Constant time
O(log n) Logarithmic time
O(n) Linear time
O(n log n) Log-linear time
O(n²) Quadratic time
O(2ⁿ) Exponential time
Asymptotic Notation
Asymptotic notation is a mathematical way to describe the efficiency(how well an algorithm uses time and memory ) of an
algorithm by expressing its running time or space in terms of input size (n) as it
grows very large.
1. Big O Notation – O(f(n))
• Defines the upper bound(maximum amount of time or space) on the
running time.
• Represents the worst-case scenario.
• If an algorithm runs in O(n²), it will not take more than cn² time for large
n.(c is constant)
Big O Notation Name
O(1) Constant
O(log n) Logarithmic
O(n) Linear
O(n log n) Linearithmic
O(n²) Quadratic
O(n³) Cubic
O(2ⁿ) Exponential
O(n!) Factorial
Example: linear search=> O(n)
[Link] Notation – Ω(f(n))
• Defines the lower bound(minimum) on the running time.
• Represents the best-case scenario.
• If an algorithm is Ω(n), it takes at least cn time for large n.
Omega Notation Name
Ω(1) Constant
Ω(log n) Logarithmic
Ω(n) Linear
Ω(n log n) Linearithmic
Ω(n²) Quadratic
Example: linear search => Ω(1)
3. Theta Notation – Θ(f(n))
• Defines the exact bound: both upper and lower.
• Represents the Average-case scenario.
• Means the algorithm runs in time that is both O(f(n)) and Ω(f(n)).
• If an algorithm is Θ(n log n), it always grows like n log n for large n.
Theta Notation Name
Θ(1) Constant
Θ(log n) Logarithmic
Θ(n) Linear
Θ(n log n) Linearithmic
Θ(n²) Quadratic
Example :Linear search => Θ(n/2) = Θ(1 × n/2) = Θ(n) ← constant is ignored
4. Little o Notation – o(f(n))
• Defines a loose upper bound or strict upper bound
• Means the algorithm grows strictly slower than f(n).
• If T(n) = o(n²), it grows slower than n², but never equals or exceeds it.
Example:
If an algorithm runs in O(n) time, and you describe it as O(n²):
• It’s not wrong, but it’s less accurate
Little o Notation Name
o(1) Strictly less than constant
o(log n) Sub-logarithmic
o(n) Sub-linear
o(n log n) Slower than linearithmic
o(n²) Sub-quadratic
o(2ⁿ) Sub-exponential
Performance Measurement Techniques
Performance measurement techniques for algorithms involve evaluating how efficiently an algorithm uses resources (like time and
memory) and how accurately it performs its task.
1)Theoretical Analysis (Asymptotic)(using mathematics)
Theoretical analysis is the process of using mathematics to evaluate how efficient an algorithm is without actually running it.
Based on: Inputsize, operations, complexity formulas
It use mathematics to estimate:
• Time Complexity (e.g., O(n), O(n²))(how fast it runs)
• Space Complexity (e.g., O(1), O(n))(how much memory it uses)
2)Empirical Analysis (After Writing Code)
Empirical analysis means testing how an algorithm performs by actually running it on a computer. It measures things like:
• Execution time
• Memory usage
• Input/output behavior
This is done using real input data and tools like timers or profilers. Unlike theoretical analysis, it depends on the programming
language, system hardware, and compiler.
Timers
A timer measures how long a program or part of it takes to run.
• Example: In Python, time() function can track how many seconds your algorithm takes.
Profilers
A profiler is a tool that gives detailed info about where time and memory are spent.
• It shows which functions are slow or memory-heavy.
• Examples: cProfile in Python, VisualVM for Java
Difference between theoretical Analysis and Empirical Analysis:
Feature Theoretical Analysis Empirical Analysis
Meaning Uses math to predict performance Tests by actually running the code
Based on Input size, operations, complexity formulas Real input, actual execution, hardware/software used
Example "Bubble sort takes O(n²) time in worst case" "Bubble sort took 0.002 seconds for 1000 elements"
When Used Before coding After coding
Accuracy General prediction Real-world performance