Asymptotic analysis

What is an Algorithm ? Lets discuss whats all the fuss is about!

An algorithm is a step-by-step set of instructions or rules to perform a specific task or solve a particular problem.
Therefore the algorithms are used in various fields, including mathematics, computer science, and everyday problem-solving. They provide a systematic and well-defined approach to solving problems, ensuring that the solution is accurate, efficient, and repeatable.

There are some key characteristics of algorithms that include:

1. Input: Algorithms take input, which is the information or data the algorithm operates on.

2. Output: Algorithms produce output, which is the result or solution generated after processing the input.

3. Definiteness: Algorithms have clear and unambiguous instructions for each step, leaving no room for ambiguity or interpretation.

4. Finiteness: Algorithms must terminate after a finite number of steps. They should not go into an infinite loop.

5. Feasibility: Algorithms describe operations that can be performed using basic operations and a finite amount of resources.

6. Effectiveness: Algorithms are designed to solve specific problems or perform particular tasks efficiently.

Algorithms can be expressed in various forms, including natural language, pseudo code, flowcharts, or specific programming languages. They serve as a fundamental concept in computer science and play a crucial role in the development of software and the design of efficient solutions for a wide range of problems.

As we are now clear what is an algorithm is, there no comes the main part!

Asymptotic analysis

Lets look at this term Asymptotic analysis :
Asymptotic analysis is a method used in computer science and mathematics to describe the behaviour of algorithms as the input size approaches infinity. The purpose of asymptotic analysis is to understand the efficiency and scalability of algorithms without being concerned with low-level details or constant factors. It provides a high-level view of the algorithm’s performance in terms of time complexity and space complexity.

Time complexity and space complexity are measures used to analyse the efficiency of algorithms. They help us understand how the performance of an algorithm scales with input size and provide insights into how much time and memory an algorithm requires.

1.Time Complexity:

• Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of the input.
• It is expressed using Big O notation (e.g., O(n), O(n^2), O(log n)), where “n” represents the size of the input.
• The goal is to describe the upper bound of the running time in the worst-case scenario.

Examples:

• O(1): Constant time complexity (e.g., accessing an element in an array by index).
• O(n): Linear time complexity (e.g., iterating through an array).
• O(n^2): Quadratic time complexity (e.g., nested loops).

2.Space Complexity:

• Space complexity is a measure of the amount of memory an algorithm uses as a function of the size of the input.
• Similar to time complexity, it is expressed using Big O notation.
• It accounts for both auxiliary space (space used by the algorithm itself) and input space.

Examples:

• O(1): Constant space complexity (e.g., using a fixed number of variables).
• O(n): Linear space complexity (e.g., using an array with “n” elements).
• O(n^2): Quadratic space complexity (e.g., using a 2D array with “n” rows and columns).

When analyzing algorithms, it’s common to consider both time and space complexity to get a comprehensive understanding of their efficiency. It’s often necessary to make trade-offs between time and space complexity based on the requirements and constraints of a specific problem or application. Algorithms with lower time and space complexity are generally considered more efficient, but the choice of algorithm depends on the specific context and requirements of the problem at hand.

Here is a short list of Time and Space complexity

Sorting Techniques:

1. Bubble Sort:

   • Time Complexity: O(n^2) (average and worst case)
   • Space Complexity: O(1)

2. Selection Sort:

   • Time Complexity: O(n^2) (average and worst case)
   • Space Complexity: O(1)

3. Insertion Sort:

   • Time Complexity: O(n^2) (average and worst case)
   • Space Complexity: O(1)

4. Merge Sort:

   • Time Complexity: O(n log n) (average and worst case)
   • Space Complexity: O(n)

5. QuickSort:

   • Time Complexity: O(n log n) (average case), O(n^2) (worst case)
   • Space Complexity: O(log n)

6. Heap Sort:

   • Time Complexity: O(n log n) (average and worst case)
   • Space Complexity: O(1)

Searching Techniques:

1. Linear Search:

   • Time Complexity: O(n) (average and worst case)
   • Space Complexity: O(1)

2. Binary Search (on a sorted array):

   • Time Complexity: O(log n) (average and worst case)
   • Space Complexity: O(1)

Inserting and Deleting Techniques:

1. Insertion in an Array:

   • Time Complexity: O(n) (average case), O(1) (best case, when inserting at the end)
   • Space Complexity: O(1)

2. Deletion in an Array:

   • Time Complexity: O(n) (average case), O(1) (best case, when deleting from the end)
   • Space Complexity: O(1)

3. Insertion in a Linked List:

   • Time Complexity: O(1) (average and worst case, when inserting at the beginning)
   • Space Complexity: O(1)

4. Deletion in a Linked List:

   • Time Complexity: O(1) (average and worst case, when deleting from the beginning)
   • Space Complexity: O(1)

These complexities are general guidelines and can vary based on specific implementations and optimizations. It’s important to choose the appropriate algorithm based on the specific requirements and constraints of the problem at hand.

let us understand the time complexity equation

So, let us say we have an algorithm described by an equation as f(n) = 3n^2 + 5n + 14

not what to think about this equation ?

so we have to understand that here n represents the number of inputs, and n^2 means that there is a loop within the loop i.e, the nested loop

so here in the above mention equation if we simplify it means, that the algorithm has a nested loop with 3 lines of code, followed by a loop with in 5 lines of code and there are 14 lines of code outside of the loop.

If you have made this far, Congratulations. You have now learned the technical terms to start your journey in solving problems with optimised solutions.