Please enable JavaScript.

Coggle requires JavaScript to display documents.

Decrease-and-Conquer - Coggle Diagram

- - - - Ex: a^n (a!=0,n>0)
        
        Relationship between a solution to an
        instance of size n and an instance of size n − 1
        
        a^n = a^(n−1) . a
        
        So, f (n) = a^n can be computed:
        
        Top Down: using its recursive definition
        
        Bottom Up: multiplying 1 by a n times
  - - - Ex: a^n(a!=0,n>0)
        
        Instance of half its size = a^(n/2)
        
        Relationship between instance of size n and an instance of size n/2
        
        a^n = (a^(n/2))^2
        
        Does not work for odd n
        
        a^n
        
        4 more items...
  - - - Based on the formula:
        
        gcd(m, n) = gcd(n, m mod n).
- - - - Now we have an n-1 sorted Array
        
        A[0] ≤ ... ≤ A[n − 2]
        
        Find an
        appropriate position for A[n − 1] among the sorted elements and insert it there.
        
        Scan the sorted subarray from right to left until the
        first element smaller than or equal to A[n − 1]
        
        insert A[n − 1]
        right after that element
  - - - A[j ]> v
        
        Number of key comparisons in the algorithm depends on the
        nature of the input
      - Asymptotic Notation
        
        BigTheta(n^2)
- - - - It solution
      - Smaller instance
        
        It solution
        
        . . .
  - - - Exploit
        
        Top Down
        
        Leads to recursive implementation
        
        Bottom Up
        
        Leads to iteratively implementation
        
        incremental approach