Definition of an Algorithm:
An algorithm is a step-by-step procedure or a set of rules designed to solve a specific problem or accomplish a defined task in a finite amount of time. It is a well-defined computational process that takes input and produces output.
*** Characteristics of an Algorithm ***
An algorithm must satisfy the following characteristics:
Input:
The algorithm should have well-defined inputs.
Inputs can be zero or more quantities.
Output:
The algorithm must produce at least one output.
The output should be the solution to the problem.
Finiteness:
The algorithm must terminate after a finite number of steps.
Infinite loops or unending calculations violate this characteristic.
Definiteness:
Each step of the algorithm must be precisely defined.
Ambiguity in any step should be avoided.
Effectiveness:
Each operation should be basic enough to be carried out by a computing agent (such as a person or a computer) in a finite amount of time.
Performance Analysis:
Performance analysis involves evaluating an algorithm based on two key criteria:
1. Time Complexity
2. Space Complexity
Time Complexity:
Time complexity refers to the amount of computational time an algorithm takes to complete as a function of the size of the input.
Growth Notations -
Big-O Notation (𝑂):
Represents the upper bound of an algorithm's running time.
Example:
𝑂(𝑛^2) for Bubble Sort in the worst case.
Big-Θ Notation (Θ)
Represents the tight bound, indicating the exact time complexity.
Example: Θ(nlogn) for Merge Sort in average and worst cases.
Big-Ω Notation (Ω)
Represents the lower bound, indicating the best-case complexity.
Example: Ω(n) for Linear Search when the element is the first item.
Common Time Complexities
Constant Time (O(1)): Accessing an element in an array.
Logarithmic Time (O(logn)): Binary Search.
Linear Time (O(n)): Linear Search.
Quadratic Time (O(n ^2)): Bubble Sort.
Exponential Time (O(2 ^n)): Solving the Tower of Hanoi problem.
Space Complexity:
Space complexity refers to the amount of memory space required by an algorithm to execute as a function of the input size.
Components of Space Complexity
Fixed Part: Space required to store constants, program variables, and instructions.
Variable Part: Space required for dynamic allocations, input size, and recursion stack.
Examples
Linear Space (O(n)): Storing a list of n elements.
Constant Space (O(1)): Swapping two variables.
#Space #Complexity #Fixed #Variable #Part #Time #Complexity #Growth #Notations #Big-O #Big-Θ #Big-Ω #Constant #Logarithmic #Linear #Quadratic #Exponential #Complexities #Performance #Analysis #Time #Space #Complexity #algorithm #Characteristics #Algorithm #well-defined #Input #Output #Finiteness #Definiteness #Effectiveness #Algorithm #definition
An algorithm is a step-by-step procedure or a set of rules designed to solve a specific problem or accomplish a defined task in a finite amount of time. It is a well-defined computational process that takes input and produces output.
*** Characteristics of an Algorithm ***
An algorithm must satisfy the following characteristics:
Input:
The algorithm should have well-defined inputs.
Inputs can be zero or more quantities.
Output:
The algorithm must produce at least one output.
The output should be the solution to the problem.
Finiteness:
The algorithm must terminate after a finite number of steps.
Infinite loops or unending calculations violate this characteristic.
Definiteness:
Each step of the algorithm must be precisely defined.
Ambiguity in any step should be avoided.
Effectiveness:
Each operation should be basic enough to be carried out by a computing agent (such as a person or a computer) in a finite amount of time.
Performance Analysis:
Performance analysis involves evaluating an algorithm based on two key criteria:
1. Time Complexity
2. Space Complexity
Time Complexity:
Time complexity refers to the amount of computational time an algorithm takes to complete as a function of the size of the input.
Growth Notations -
Big-O Notation (𝑂):
Represents the upper bound of an algorithm's running time.
Example:
𝑂(𝑛^2) for Bubble Sort in the worst case.
Big-Θ Notation (Θ)
Represents the tight bound, indicating the exact time complexity.
Example: Θ(nlogn) for Merge Sort in average and worst cases.
Big-Ω Notation (Ω)
Represents the lower bound, indicating the best-case complexity.
Example: Ω(n) for Linear Search when the element is the first item.
Common Time Complexities
Constant Time (O(1)): Accessing an element in an array.
Logarithmic Time (O(logn)): Binary Search.
Linear Time (O(n)): Linear Search.
Quadratic Time (O(n ^2)): Bubble Sort.
Exponential Time (O(2 ^n)): Solving the Tower of Hanoi problem.
Space Complexity:
Space complexity refers to the amount of memory space required by an algorithm to execute as a function of the input size.
Components of Space Complexity
Fixed Part: Space required to store constants, program variables, and instructions.
Variable Part: Space required for dynamic allocations, input size, and recursion stack.
Examples
Linear Space (O(n)): Storing a list of n elements.
Constant Space (O(1)): Swapping two variables.
#Space #Complexity #Fixed #Variable #Part #Time #Complexity #Growth #Notations #Big-O #Big-Θ #Big-Ω #Constant #Logarithmic #Linear #Quadratic #Exponential #Complexities #Performance #Analysis #Time #Space #Complexity #algorithm #Characteristics #Algorithm #well-defined #Input #Output #Finiteness #Definiteness #Effectiveness #Algorithm #definition
Comments
Post a Comment