ASSIGNMENT-1
Revisiting Space/Time Complexity and Asymptotic
Notations:
An algorithm is a finite sequence of well-defined instructions, typically used to solve a class
of specific problems or to perform a computation.
Components of an Algorithm:
Input: The data provided to the algorithm for processing.
Output: The result produced by the algorithm after processing the input.
Algorithm Representation Methods:
Natural Language: Describing algorithms using everyday language, which can
sometimes lead to ambiguity.
Pseudocode: A high-level description of an algorithm using the structural
conventions of programming languages but in plain language.
Flowcharts: Diagrammatic representations that illustrate the sequence of
operations in an algorithm.
Objectives of Algorithm Design:
Correctness: Ensuring the algorithm produces the expected output for all valid
inputs.
Efficiency: Optimizing the algorithm to use minimal computational resources, such
as time and memory.
Example Algorithm: Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm.
Algorithm BubbleSort(A, n)
Input: Array A of n elements
Output: Array A sorted in ascending order
for i ← 0 to n-1 do
for j ← 0 to n-i-2 do
if A[j] > A[j+1] then
CO23317
ASSIGNMENT-1
swap A[j] and A[j+1]
Analysis of Algorithms:
Time Complexity: Measures the amount of time an algorithm takes to complete as a
function of the input size.
Space Complexity: Measures the amount of memory an algorithm uses during its
execution.
Asymptotic Notations:
Big O Notation (O): Describes the upper bound of the time complexity,
representing the worst-case scenario.
Omega Notation (Ω): Describes the lower bound, representing the best-case
scenario.
Theta Notation (Θ): Describes a tight bound, indicating that the time complexity is
both upper and lower bounded by the same function.
Common Time Complexities:
O(1): Constant time – the algorithm's execution time does not depend on the input
size.
O(n): Linear time – execution time grows linearly with the input size.
O(n²): Quadratic time – execution time grows quadratically with the input size.
O(log n): Logarithmic time – execution time grows logarithmically as the input size
increases.
O(2ⁿ): Exponential time – execution time doubles with each additional input
element.
Graphical Representation of Time Complexities:
To visualize how different time complexities grow with input size, consider the following
graph:
In this graph:
O(1) remains constant regardless of input size.
O(log n) grows slowly as input size increases.
O(n) grows linearly with input size.
O(n log n) grows faster than linear but slower than quadratic.
CO23317
ASSIGNMENT-1
O(n²) grows quadratically, becoming quite large for larger inputs.
O(2ⁿ) grows exponentially, becoming impractical for relatively small input sizes.
Graphs and Visuals
Graphs depicting time complexity growth for various algorithms will be included here.
Experimental Studies vs. Theoretical Analysis
Experimental Studies:
- Implement the algorithm and run it with various inputs.
- Measure the runtime using tools like `System.currentTimeMillis()` or a stopwatch.
- Limitations include implementation complexity and lack of generalization.
Theoretical Analysis:
- Uses high-level descriptions instead of actual implementation.
- Provides a mathematical characterization of running time as a function of input size.
- Independent of hardware and software specifics.
Pseudocode Example: Finding Maximum Element
Algorithm arrayMax(A, n)
Input: array A of n integers
Output: maximum element of A
currentMax ← A[0]
for I ← 1 to n – 1 do
if A[I] > currentMax then
currentMax ← A[I]
return currentMax
Performance Analysis
Criteria: Time complexity and space complexity.
Time Complexity: Total time required to execute an algorithm.
- Fixed part: Compile time, independent of input.
- Variable part: Runtime, dependent on input size.
CO23317
ASSIGNMENT-1
Space Complexity: Total memory required by the algorithm.
- Fixed part: Instruction space, constants, etc.
- Variable part: Memory required for input/output and temporary storage.
Asymptotic Notations
Big O Notation (O):
- Represents the upper bound of an algorithm's running time.
- Describes the worst-case scenario.
Omega Notation (Ω):
- Represents the lower bound of an algorithm's running time.
- Describes the best-case scenario.
Theta Notation (Θ):
- Represents a tight bound on the running time of an algorithm.
- Indicates the algorithm's running time grows at the same rate for both upper and lower
bounds.
Graph: Growth of Time Complexity Classes
The graph below illustrates the growth rates of different time complexity classes.
CO23317
