Set of sequence of unambiguous instructions for solving a problem.
Characteristics
Zero or more inputs: “hello world” program zero inputs
Definiteness: Each step should be precise and unambiguous
Output: At least one output
Effectiveness: Each step should be precise and feasible
Finiteness: Terminates after finite number of steps
We write algorithms in pseudo-code: A mix of natural and programming language
# Example: swap two numbers (a, b)Algorithm swap(a,b)Begin: temp = a; a = b; b = temp;End:
We can use {} in the place of Begin: and End:
The = token may also be written as := and ←
Fundamentals of Problem Solving
This is the framework for analyzing algorithms to solve new problems.
Understand the Problem
Clearly define:
input
expected output
Consider the constraints and assumptions
Ensure the problem is well defined and unambiguous
Decide on the Computational Means
Choose the appropriate model: PRAM, RAM, < TM >
Evaluate the hardware and software constraints
Exact v/s Approximate problem solving
Decide if the exact solution is feasible, or necessary
Computational cost
Algorithmic Design Techniques
Brute Force
Divide and Conquer
Decrease and Conquer
Transform and Conquer
Dynamic Programming
Greedy Technique
Branch and Bound
Backtracking
Designing an Algorithm
Step by step: pseudocode
Algorithm follows all the characteristics
Break into subroutines
Proving Algorithm Correctness: Works for all valid inputs
Analyze the algorithm
Timer Complexity
Space Complexity
Test and Debug: Test for all the cases
Documenting the algorithm
Improving and Refinement
Ways to Analyse
Time Efficiency/Complexity: how long to run as input size grows
Space Efficiency/Complexity: how much memory consumed as input size grows
Network Efficiency/Complexity
Hardware (Power) Efficiency/Complexity
Analyse Time and Space for
Example
Time: measure every statement as 1 unit of time
Space: Frequency count of variables when algorithms are small
Algorithm swap(a,b)Begin: temp <- a; (1t) a <- b; (1t) b <- temp; (1t)End:
T(n) = 1+1+1 = 3 = constant
S(n) = 1+1+1 = 3 = constant
We can represent this in the order of O(1)
Example
Notice the difference when we have a loop:
Algorithm sum(A,n)Begin: s=0; for (i=0, i<n, i++) // checks upto 'n+1' times, i++ 'n' times s = s + A[i] // repeats upto n times return s;End:
The dominant term is checking the condition (n+1). Consider only this
(2n+2) → n+1; the +2 becomes insignificant as n increases
So: T(n+1) → O(n)
Time Complexities with Sample Values
Symbol
Name
n = 1
n = 10
n = 100
n = 1000
n = 10000
O(1)
Constant Time
1
1
1
1
1
O(log n)
Logarithmic
0
2
6
9
13
O(sqrt(n))
Sublinear
1
3
10
31
100
O(n)
Linear
1
10
100
1000
10000
O(n logn)
Linearithmic
0
33
664
9965
132877
O(n^2)
Quadratic
1
100
10000
1000000
100000000
O(n^3)
Cubic
1
1000
1000000
1000000000
1000000000000
O(2^n)
Exponential
2
1024
~1.27e30
~1.07e301
Overflow
O(n!)
Factorial
1
3.63e6
Overflow
Overflow
Overflow
Algorithmic Analysis Framework
1. Space Complexity
S(p) = C + SP(I)
P is the problem
C is the constants
I talks about instance characteristics
2. Time Complexity
Big O, Step Count Method
3. Measuring Input Size
Efficiency of the algorithm → func
t(n) = n
S(n) parameters a function takes
4. Measuring Run Time
Identify the basic operation
Understand the concept of basic operation
Compute total time taken for the operation
T(n) is Cop x C(n)
5. Compute the Order of Growth
Measure the performance of the algorithm in relation with input size, we must analyze for all cases of n
Asymptotic Notation
Asymptotic notations describe the growth of functions, often used in analyzing the time and space complexity of algorithms.
Upper Bound
Big O provides the upper bound of an algorithm’s running time, guaranteeing it won’t exceed a certain rate of growth.
Info
The function (t(n)=O(g(n))) if and only if there exist constants (C>0) and (n0≥0) such that: [t(n)≤C⋅g(n),∀n≥n0]
Example: (t(n)=3n+2) is (O(n)), as (t(n)≤4n) for (n≥1) (with (C=4,n0=1)).
Lower Bound
Omega provides the lower bound of an algorithm’s running time, guaranteeing it takes at least a certain amount of time.
Info
The function (t(n)=Ω(g(n))) if and only if there exist constants (C>0) and (n0≥0) such that: [t(n)≥C⋅g(n),∀n≥n0]
Example: (t(n)=3n+2) is (Ω(n)), as (t(n)≥3n) for (n≥1) (with (C=3,n0=1))
Tight Bound
Theta provides both the upper and lower bounds, tightly bounding the growth of an algorithm’s running time.
Info
The function (t(n)=Θ(g(n))) if and only if there exist constants (C1,C2>0) and (n0≥0) such that: [C1⋅g(n)≤t(n)≤C2⋅g(n),∀n≥n0]
Example: (t(n)=3n+2) is (Θ(n)), as (3n≤t(n)≤4n) for (n≥1).
Small o and Small ω
These notations describe stricter bounds compared to Big O and Omega.
Small (o)
(tn=o(gn)) means that (tn) grows asymptotically slower than (gn):
[limn→∞gntn=0]
Small (ω)
(tn=ω(gn)) means that (tn) grows asymptotically faster than (gn):
[limn→∞gntn=∞]
Summary
Notation
Description
Usage
(O)
Upper bound
Guarantees worst-case runtime
(Ω)
Lower bound
Guarantees minimum runtime
(Θ)
Tight bound
Represents average-case runtime
(o)
Strict upper bound
Stricter than Big O
(ω)
Strict lower bound
Stricter than Omega
Analysis of Non-Recursive Algorithms
Q: Find the maximum element of an array of size ‘n’
Algorithm find_max(A, n)Begin: max_element <- A[0]; for i <- 1 to n-1 do: // (n-1 times) if A[i] > max_element then: max_element <- A[i]; // (1t) larger element is found return max_element;End:
Input size: n (size of the array).
Basic Operation: Comparison (comparing the current element with the maximum element).
C(n): The algorithm performs one comparison for each element