Data Structures and Algorithms B
  • Introduction
  • Stable Marrage
  • Huffman Codes
    • ABL
    • Implementation
  • Graph Algorithms
    • Connect Component
    • Bipartiteness
    • Strongly Connected Components
      • Implementation
    • Topological Sort
      • Implementation 1
      • Implementation 2
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
      • Prims
        • Implementation 1
      • Kruskels
        • Implementation 1
      • Traveling Salesman Problem
    • k-Clustering
    • Dynamic Programming with Trees
      • Implementation 1
      • Implementation 2
    • Disjoint Sets
      • Implementation
    • Eularian Cycle
      • Implementation
    • Hamiltonian Path
      • Implementation
  • Divide and Conquer
    • Merge Sort
    • Integer Multiplication
    • Closest Pair
    • Master Method
  • Dynamic Programming
    • Interval Scheduling
    • Knapsack Problem
  • Network Flow
    • Maximum Network Flow
    • Improvements
    • Image Segmentation
  • String Algorithms
    • Z Algorithm
    • Boyer-Moore
    • Knuth-Morris-Pratt
    • Suffix Trees
      • Naive Implementation
      • Ukkonens Algorithm
        • Implementation
      • Applications
        • Longest Common Substring
        • Longest Palindromic Substring
        • Longest Repeated Substring
  • Randomized Algorithms
    • Bloom Filters
      • Implementation
Powered by GitBook
On this page
  • Input
  • Output
  • Algorithm Space
  • Karatsubu Multiplication

Was this helpful?

  1. Divide and Conquer

Integer Multiplication

Input

  • Two n digit numbers x and y.

Output

  • x∗yx * yx∗y;product.

Algorithm Space

  • In grade school we've been taught well defined set of rules to follow for integer multiplication.

  • Time complexity analysis of grade-school algorithm:

    • Given number A with n digits, and number B with y digits, for each number in y, we multiply with n. Then we add the numbers together.

    • This gives us a total of O(∣A∣∗∣B∣+c)O(|A| * |B| + c)O(∣A∣∗∣B∣+c)

    • Or O(n2)O(n^2)O(n2)

Karatsubu Multiplication

  • Algorithm is not exactly intuitive so I wont go through it.

  • But the main idea is that the algorithm space is large, and there are different design methods to solve a problem.

  • Can be optimized to remove one recursive call, and increase its running time performance.

PreviousMerge SortNextClosest Pair

Last updated 5 years ago

Was this helpful?