#ALGO  #DSA 

1. Understanding DSA:

Data Structures refer to the organization and management of data in a way that enables efficient access and modification.

Algorithms, on the other hand, are step-by-step procedures designed to solve specific problems.

Together, they provide a powerful toolkit for programmers to tackle complex computational challenges

1.1 Importance of DSA

https://www.linkedin.com/pulse/importance-data-structures-algorithms-dsa-tech-industry-devesh-raj/

Efficiency: DSA allows us to optimize resource usage, such as time and memory.

Scalability: As data volumes grow exponentially, the ability to handle large-scale operations becomes crucial. DSA equips developers with techniques to efficiently manage and manipulate data.

Problem-Solving: DSA provides a systematic approach to problem-solving. It helps break down complex problems into smaller, more manageable components, allowing for easier analysis and solution design.

1.2 What is Algorithm?

  • An algorithm is a step-by-step procedures designed to solve specific problems.
  • Algorithm is not the complete code or program, it is just the core logic(solution) of a problem,
  • It can be expressed either as an informal high level description as pseudocode or using a flowchart

1.3 How to compare two Algorithm

The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm.

1. Execution time

  • Not a good measure
  • As execution time are specific to a particular computer

2. No. of statement executed

  • Not a good measure
  • As no of statement varies with the programming language as well as on the style of individual programmer.

3. Asymptotic analysis

  • Ideal solution
  • Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input size increases.
  • With the increase in the input size, the performance also changes, i.e. time or space taken by an algorithm increases

1.4 Why performance analysis?

There are many important things that should be taken care of, like user-friendliness, modularity, security, maintainability, etc But we worry about performance because we can have all the above things only if we have performance.

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space

Performance is measured based on:

  • Time Complexity
    • Time Complexity is a way to represent the amount of time required by the program to run till its completion.
  • Space Complexity
    • It’s the amount of memory space required by the algorithm, during the course of its execution.

1.5 Does Asymptotic Analysis always work?

https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/

Asymptotic Analysis is not perfect, but that’s the best way available for analyzing algorithms.

For example, say there are two sorting algorithms that take 1000nLogn and 2nLogn time respectively on a machine. Both of these algorithms are asymptotically same (order of growth is nLogn)

With Asymptotic Analysis, we can’t judge which one is better as we ignore constants in Asymptotic Analysis

1.6 How to measure performance?

https://www.programiz.com/dsa/asymptotic-notations

https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis.htm

Performance of an algo is denoted by Asymptotic Notations.

Asymptotic Notations is a mathematical way to represent time complexity of an Algo.

# Types
1. Big-O notation
2. Omega notation
3. Theta notation

Big Oh, O: Asymptotic Upper Bound

https://www.javatpoint.com/data-structure-asymptotic-analysis

The notation Ο(n) is the formal way to express the least upper bound of an algorithm’s running time. It is the most commonly used notation.

It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

O(g(n)) = { f(n): there exist positive constants c and n0
            such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

If f(n) and g(n) are the two functions defined for positive integers, then f(n) = O(g(n)) as f(n) is big oh of g(n) or f(n) is on the order of g(n) if there exists constants c and no such that f(n) ≤ c.g(n) for all n≥no

Let us consider a given function, f(n)=4.n^3+10.n^2+5.n+1

Considering g(n)=n^3
f(n) <= 5.g(n) for all the values of n>2

Hence, the complexity of f(n) can be represented as O(g(n)) i.e. O(n^3)

Big Omega, Ω: Asymptotic Lower Bound

It basically describes the best-case scenario which is opposite to big O notation.

It is the formal way to represent the lower bound of an algorithm’s running time. It measures the best amount of time an algorithm can possibly take to complete or the best-case time complexity.

Ω(g(n)) = { f(n): there exist positive constants c and n0 
            such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

Let us consider a given function, f(n)=4.n^3+10.n^2+5.n+1

Considering g(n)=n3, 
f(n) >= 4.g(n) for all the values of n>0

Hence, the complexity of f(n) can be represented as Ω(g(n)) i.e. Ω(n3)

Theta, θ: Asymptotic Tight Bound

The theta notation mainly describes the average case scenarios

It represents the realistic time complexity of an algorithm. Every time, an algorithm does not perform worst or best, in real-world problems, algorithms mainly fluctuate between the worst-case and best-case, and this gives us the average case of the algorithm.

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0
            such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

Let us consider a given function, f(n)=4.n3+10.n2+5.n+1

Considering g(n)=n3
4.g(n) <= f(n) <= 5.g(n) for all the large values of n.

Hence, the complexity of f(n) can be represented as θ(g(n)), i.e. θ(n3)

Common Asymptotic Notations

Notation Name
O(1) Constant
O(logn) Logarithmic
O(n) Linear
O(nlogn) Linear Logarithmic
O(n*n) Quadralic
O(n* n *n) Cubic
O(c^n) Exponential
O(n!) Factorial

Algorithm can be of two types

  • Iterative
    • Calculate time Complexity
      • 01_TC_itr.png
  • Recursive
    • Any function which calls itself with a failure condition is called recursive
    • Calculate time Complexity
      • Back Substitution Method
      • Recursion Tree Method
      • Master Theorem
        • 01_TC_rec.png

Iterative vs Recursive

  • Iterative
    • Terminates when a condition is proven to be false
    • Each iteration does not require extra space
    • An infinite loop may run forever
  • Recursive
    • Terminates when a base condition is reached
    • Each recursive call requires extra space on the stack frame
    • An infinite loop may lead to run out of memory
    • Eg: Fibonacci, Merge sort, Quick sort, DFS, BFS, Inorder, Preorder, Postorder etc
  • NOTE:
    • For some problem there is no obvious iterative algorithm

Searching Algorithms

  1. Linear/Sequential Search

    • For Unsorted small array or list
    • Sequential access
    • Time complexity is O(n)

  2. Binary Search

    • For large sorted arrays or list
    • Random access
    • Time complexity of O(log n)

Sorting Algorithm

  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Merge Sort
  • Quick Sort

Reference