Scribd
Upload
14 views2 pages

Algorithms, Time Complexity

The document provides an introduction to algorithms, defining them as step-by-step procedures for problem-solving with key concepts including input, output, definiteness, finiteness, and effectiveness. It categorizes algorithms into types such as brute force, divide and conquer, greedy, dynamic programming, and backtracking, while also discussing time complexity and common time complexities using Big O notation. Additionally, it emphasizes the importance of understanding algorithms and their complexities for efficient program design.

Uploaded by

MEENU
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views2 pages

Algorithms, Time Complexity

The document provides an introduction to algorithms, defining them as step-by-step procedures for problem-solving with key concepts including input, output, definiteness, finiteness, and effectiveness. It categorizes algorithms into types such as brute force, divide and conquer, greedy, dynamic programming, and backtracking, while also discussing time complexity and common time complexities using Big O notation. Additionally, it emphasizes the importance of understanding algorithms and their complexities for efficient program design.

Uploaded by

MEENU
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Introduction to Algorithms

Algorithm: An algorithm is a step-by-step procedure or formula for solving a problem. It is a set of


instructions designed to perform a specific task.

Key Concepts

1. Input: The algorithm receives input.


2. Output: The algorithm produces output.
3. Definiteness: Each step of the algorithm is precisely defined.
4. Finiteness: The algorithm terminates after a finite number of steps.
5. Effectiveness: Each step of the algorithm is basic enough to be carried out.

Types of Algorithms

1. Brute Force Algorithms: Solve the problem through exhaustive search.


2. Divide and Conquer Algorithms: Break the problem into smaller sub-problems, solve each sub-
problem, and combine the solutions.
3. Greedy Algorithms: Make the locally optimal choice at each step.
4. Dynamic Programming Algorithms: Break the problem into sub-problems and solve each sub-
problem only once, storing the solutions.
5. Backtracking Algorithms: Build a solution incrementally and abandon a solution as soon as it is
determined that this solution cannot be completed.

Time Complexity

Time Complexity: A measure of the amount of computational time that an algorithm takes to
complete as a function of the length of the input. Time complexity is a type of computational complexity
that describes the time required to execute an algorithm. The time complexity of an algorithm is the amount of
time it takes for each statement to complete. As a result, it is highly dependent on the size of the processed data.

Common Time Complexities

1. Constant Time - O(1): The running time is independent of the input size.
2. Logarithmic Time - O(log n): The running time grows logarithmically with the input size.
3. Linear Time - O(n): The running time grows linearly with the input size.
4. Linearithmic Time - O(n log n): The running time grows in proportion to n log n.
5. Quadratic Time - O(n^2): The running time grows quadratically with the input size.
6. Cubic Time - O(n^3): The running time grows cubically with the input size.
7. Exponential Time - O(2^n): The running time grows exponentially with the input size.
8. Factorial Time - O(n!): The running time grows factorially with the input size.

Examples of Algorithms and Their Time Complexities

1. Binary Search: O(log n)


2. Merge Sort: O(n log n)
3. Quick Sort: O(n log n) on average
4. Bubble Sort: O(n^2)
5. Fibonacci Sequence (using recursion): O(2^n)

Big O Notation

Big O Notation is used to classify algorithms according to how their run time or space requirements grow as
the input size grows.

 O(1): Constant time


 O(log n): Logarithmic time
 O(n): Linear time
 O(n log n): Linearithmic time
 O(n^2): Quadratic time
 O(2^n): Exponential time
 O(n!): Factorial time

Space Complexity

Space Complexity: A measure of the amount of working storage an algorithm needs.

Examples of Space Complexities

1. O(1): Constant space


2. O(n): Linear space
3. O(n^2): Quadratic space

Conclusion

Understanding algorithms and their time complexities is crucial for designing efficient programs. By
analyzing the time and space complexity, we can predict the performance of algorithms and choose the most
appropriate one for a given problem.

You might also like