Pro Programming

Professional way of Programming

  • Home
  • C MCQs
  • C
  • C++
  • C#
  • Java
  • Python
  • MySQL
  • Topics
    • Arrays
    • Strings
    • Link Lists
    • Trees
    • Shapes
  • Projects
  • Articles
  • Games
You are here: Home / Archives for CS Subjects ▼

Advance Master Theorem for Divide and Conquer Recurrences

Leave a Comment


Master Theorem is used to determine running time of algorithms (divide and conquer algorithms) in terms of asymptotic notations.
Consider a problem that be solved using recursion.


function f(input x size n)
if(n > k)
solve x directly and return 
else
divide x into a subproblems of size n/b
call f recursively to solve each subproblem
Combine the results of all sub-problems

The above algorithm divides the problem into a subproblems, each of size n/b and solve them recursively to compute the problem and the extra work done for problem is given by f(n), i.e., the time to create the subproblems and combine their results in the above procedure.

So, according to master theorem the runtime of the above algorithm can be expressed as:


T(n) = aT(n/b) + f(n)   

where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
f(n) = cost of work done outside the recursive calls like dividing into subproblems and cost of combining them to get the solution.

Not all recurrence relations can be solved with the use of the master theorem i.e. if


  • T(n) is not monotone, ex: T(n) = sin n
  • f(n) is not a polynomial, ex: T(n) = 2T(n/2) + 2n

This theorem is an advance version of master theorem that can be used to determine running time of divide and conquer algorithms if the recurrence is of the following form :-

where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
b > 1, k >= 0 and p is a real number.

Then,

  1. if a > bk, then T(n) = θ(nlogba)
  2. if a = bk, then
    (a) if p > -1, then T(n) = θ(nlogba logp+1n)
    (b) if p = -1, then T(n) = θ(nlogba loglogn)
    (c) if p < -1, then T(n) = θ(nlogba)
  3. if a < bk, then
    (a) if p >= 0, then T(n) = θ(nk logpn)
    (b) if p < 0, then T(n) = θ(nk)

Time Complexity Analysis –

  • Example-1: Binary Search – T(n) = T(n/2) + O(1)
    a = 1, b = 2, k = 0 and p = 0
    bk = 1. So, a = bk and p > -1 [Case 2.(a)]
    T(n) = θ(nlogba logp+1n)
    T(n) = θ(logn)
  • Example-2: Merge Sort – T(n) = 2T(n/2) + O(n)
    a = 2, b = 2, k = 1, p = 0
    bk = 1. So, a = bk and p > -1 [Case 2.(a)]
    T(n) = θ(nlogba logp+1n)
    T(n) = θ(nlogn)
  • Example-3: T(n) = 3T(n/2) + n2
    a = 3, b = 2, k = 2, p = 0
    bk = 4. So, a < bk and p = 0 [Case 3.(a)]
    T(n) = θ(nk logpn)
    T(n) = θ(n2)
  • Example-4: T(n) = 3T(n/2) + log2n
    a = 3, b = 2, k = 0, p = 2
    bk = 1. So, a > bk [Case 1]
    T(n) = θ(nlogba )
    T(n) = θ(nlog23)
  • Example-5: T(n) = 2T(n/2) + nlog2n
    a = 2, b = 2, k = 1, p = 2
    bk = 1. So, a = bk [Case 2.(a)]
    T(n) = θ(nlogbalogp+1n )
    T(n) = θ(nlog22log3n)
    T(n) = θ(nlog3n)
  • Example-6: T(n) = 2nT(n/2) + nn
    This recurrence can’t be solved using above method since function is not of form T(n) = aT(n/b) + θ(nk logpn)

GATE Practice questions –



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.


Post navigation









Source link

Filed Under: c programming Tagged With: •   Dynamic Programming, About Us, Advanced Data Structure, Advanced Data Structures, Advanced Topics, Algo ▼, Algorithm Paradigms ►, Algorithms, All Algorithms, All Data Structures, Amazon, Amortized analysis for increment in counter, Analysis, Analysis of Algorithms, Analysis of Algorithms | Big-O analysis, Analysis of different sorting techniques, Aptitude, Array, Arrays, Backtracking, Basic, BFS, Binary Search, Binary Search Tree, Binary Search Tree and AVL tree, Binary Tree, Bit Algorithms, Bit Magic, Branch & Bound, C, C++ Quiz, Campus Ambassador Program, Careers, Click here for more, Coding Practice, Common Interview Puzzles, Company Prep, Company Preparation, Company Specific Practice, Company-wise, Competitive Programming, Compiler Design, Complexity of different operations in Binary tree, Computer Graphics, Computer Networks, Computer Organization, Computer Organization & Architecture, Contact Us, Contests, contribute.geeksforgeeks.org, contributed articles, CPP-Library, CS Subjects, CS Subjects ▼, CS Subjectwise ►, Data Structures, DBMS, Design Patterns, Detect a negative cycle., DFS, Dictionary, Different types of recurrence relations and their solutions, Difficulty Level - Basic, Difficulty Level - Easy, Difficulty Level - Hard, Difficulty Level - Medium, Difficulty Level - School, Digital Electronics, Divide & Conquer, Divide and Conquer, DS ▼, Easy, Engg. Mathematics, Engineering Mathematics, Experienced, Experienced Interviews, Expert, Explore More..., G-Facts, Game Theory, GATE ▼, Gate 2018 Important Dates and Links, GATE CS, GATE CS 2009 | Question 35, GATE CS Corner, GATE CS Notes, GATE IT 2008 | Question 42, GATE Notes, GATE-CS-2017 (Set 2) | Question 56, GBlog, Geek of the Month, Geek on the Top, Geometric, Geometric Algorithms, GQ Home Page, Graph, Graph Algorithms, Greedy Algorithms, Hard, Hash, Hashing, Heap, HeapSort, How to begin with Competitive Programming?, How to pick a difficulty level?, How to prepare for ACM-ICPC?, How to write an Interview Experience?, HTML & XML, ide.geeksforgeeks.org, Image Processing, Insertion Sort, Internship, Internship Interviews, Internships @ GeeksforGeeks, Interview ▼, Interview Corner, Interview Experiences, ISRO, Java, java-stream, JavaScript, Languages, Languages ►, Languages ▼, Last Minute Notes, Leaderboard !!, Linked Lists, LinkedList, LMNs, Login, Longest Palindromic Subsequence, Longest Repeated Subsequence, Loop Invariant Condition with Examples of Sorting Algorithms, Master Theorem, Mathematical, Mathematical Algorithms, Matrix, Medium, MergeSort, Microsoft, Multiple Choice Quizzes, Must Do Coding Questions Company-wise, Must Do Coding Questions Topic-wise, Number Theory, number-digits, Official Papers, Operating Systems, Pattern Searching, PHP, Placement Course, Placements Preparation Course, Practice Company Questions, Practice Questions on Time Complexity Analysis, Practice Set for Recurrence Relations, Privacy Policy, Program Output, Project, Project Ideas, Puzzles, Python, Python List, QA - Placement Quizzes, Queue, QuickSort, Quiz Corner, Quizzes ▼, Randomized Algorithms, Recent Interview Experiences, Recursion, Reverse a linked list, Samsung, School Programming, Searching, Searching Algorithms, series, Set, Set to Array in Java, Skip to content, Software Design Patterns, Software Engineering, Some rights reserved, Sorting, Sorting Algorithms, SQL, Stack, Statistical Algorithms, Step by Step Guide for Placement Preparation, Step by Step Preparation, STL, Strings, Students ▼, Subjective Problems, Subjective Questions, Technical Scripter, Testimonials, Theory of Computation, Time Complexity Analysis | Tower Of Hanoi (Recursion), Time taken by Loop unrolling vs Normal loop, Top 10 Algorithms and Data Structures for Competitive Programming, Top 10 algorithms in Interview Questions, Top Topics, Topic-wise, Topic-wise Practice, Topicwise ►, Tree based DS ►, Trees, Tuple, UGC-NET, Video Tutorials, Videos, Web Technologies, Web Technology, What’s Difference?, What’s New?, Write an Article

Restoring Division Algorithm For Unsigned Integer

Leave a Comment


A division algorithm provides a quotient and a remainder when we divide two number. They are generally of two type slow algorithm and fast algorithm. Slow division algorithm are restoring, non-restoring, non-performing restoring, SRT algorithm and under fast comes Newton–Raphson and Goldschmidt.

In this article, will be performing restoring algorithm for unsigned integer. Restoring term is due to fact that value of register A is restored after each iteration.

Here, register Q contain quotient and register A contain remainder. Here, n-bit dividend is loaded in Q and divisor is loaded in M. Value of Register is initially kept 0 and this is the register whose value is restored during iteration due to which it is named Restoring.

Let’s pick the step involved:

  • Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)
  • Step-2: Then the content of register A and Q is shifted right as if they are a single unit
  • Step-3: Then content of register M is subtracted from A and result is stored in A
  • Step-4: Then the most significant bit of the A is checked if it is 0 the least significant bit of Q is set to 1 otherwise if it is 1 the least significant bit of Q is set to 0 and value of register A is restored i.e the value of A before the subtraction with M
  • Step-5: The value of counter n is decremented
  • Step-6: If the value of n becomes zero we get of the loop otherwise we repeat fro step 2
  • Step-7: Finally, the register Q contain the quotient and A contain remainder

Examples:

Perform Division Restoring Algorithm 
Dividend = 11
Divisor  = 3

nMAQOperation
400011000001011initialize
0001100001011_shift left AQ
0001111110011_A=A-M
00011000010110Q[0]=0 And restore A
30001100010110_shift left AQ
0001111111110_A=A-M
00011000101100Q[0]=0
20001100101100_shift left AQ
0001100010100_A=A-M
00011000101001Q[0]=1
10001100101001_shift left AQ
0001100010001_A=A-M
00011000100011Q[0]=1

Remember to restore the value of A most significant bit of A is 1. As that register Q contain the quotient, i.e. 3 and register A contain remainder 2.



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.


Post navigation









Source link

Filed Under: c programming Tagged With: •   Dynamic Programming, About Us, Addressing Modes, Advanced Data Structure, Advanced Data Structures, Advanced Topics, Algo ▼, Algorithm Paradigms ►, Algorithms, All Algorithms, All Data Structures, Amazon, Analysis of Algorithms, Aptitude, Array, Arrays, Backtracking, BFS, Binary Search, Binary Search Tree, Binary to Decimal Conversion, Binary to Hexadecimal Conversion, Binary to Octal Conversion, Binary Tree, Bit Algorithms, Bit Magic, Branch & Bound, C, C++ Quiz, Cache Memory, Cache Organization, Campus Ambassador Program, Careers, Clusters In Computer Organisation, Company Prep, Company-wise, Competitive Programming, Compiler Design, Computer Architecture | Flynn’s taxonomy, Computer Arithmetic | Set – 1, Computer Arithmetic | Set – 2, Computer Networks, Computer Organization, Computer Organization & Architecture, Computer Organization | Booth’s Algorithm, Computer Organization | Different Instruction Cycles, Computer Organization | Hardwired v/s Micro-programmed Control Unit, Computer Organization | Micro-Operation, Contact Us, Contests, contribute.geeksforgeeks.org, contributed articles, CPP-Library, CS Subjects, CS Subjects ▼, CS Subjectwise ►, Data Structures, DBMS, Decimal to Binary Conversion, Dependencies and Data Hazard, Design Patterns, Detect a negative cycle., DFS, Dictionary, Difference between 1’s complement and 2’s complement, Digital Electronics, Digital Electronics & Logic Design, Divide & Conquer, Divide and Conquer, DS ▼, Engg. Mathematics, Execution, Experienced, Experienced Interviews, Explore More..., Floating Point Representation, Game Theory, GATE ▼, Gate 2018 Important Dates and Links, GATE CS, GATE CS Corner, GATE CS Notes, GATE Notes, GBlog, Geek of the Month, Geek on the Top, Geometric, Geometric Algorithms, Graph, Graph Algorithms, Greedy Algorithms, Hash, Hashing, Heap, HeapSort, How to begin with Competitive Programming?, How to prepare for ACM-ICPC?, HTML & XML, I/O Interface (Interrupt and DMA Mode), ide.geeksforgeeks.org, Insertion Sort, Internship, Internship Interviews, Interview ▼, Interview Experiences, Introduction to quantum computing, ISRO, Java, java-stream, JavaScript, Languages, Languages ►, Languages ▼, Last Minute Notes, Linked Lists, LinkedList, Login, Longest Palindromic Subsequence, Longest Repeated Subsequence, Machine Instructions, Mathematical, Mathematical Algorithms, Matrix, MCQ / Quizzes, MergeSort, Microsoft, MongoDB Python | Insert and Update Data, Multiple Choice Quizzes, Number System and Base Conversions, Number Theory, number-digits, Octal to Decimal Conversion, Official Papers, Operating Systems, Pattern Searching, PHP, Placement Course, Practice Company Questions, Practice Problems, Priority Interrupts | (S/W Polling and Daisy Chaining), Privacy Policy, Program Output, Project, Puzzles, Python, Python List, QA - Placement Quizzes, Queue, QuickSort, Quizzes ▼, Randomized Algorithms, Recent Articles, Recursion, Reverse a linked list, School Programming, Searching, Searching Algorithms, series, Set, Set to Array in Java, Simplified Instructional Computer (SIC), Skip to content, Software Engineering, Some rights reserved, Sorting, Sorting Algorithms, SQL, Stack, Stages and Throughput, Statistical Algorithms, Step by Step Guide for Placement Preparation, STL, Strings, Students ▼, Subjective Questions, Technical Scripter, Testimonials, Theory of Computation, Top 10 Algorithms and Data Structures for Competitive Programming, Top 10 algorithms in Interview Questions, Top Topics, Topic-wise, Topicwise ►, Tree based DS ►, Trees, Tuple, Types and Stalling, UGC-NET, Video Tutorials, Videos, Web Technologies, Web Technology, What’s difference between CPU Cache and TLB?, What’s Difference?, What’s New?, Write an Article

Popular Posts

  • C++ program to implement Stack using Linked List 2,291 views
  • Patterns and Shapes C++ 1,187 views
  • Heap Sort Implementation in C++ 1,002 views
  • Free Download W3Schools Offline Version 2017 966 views
  • Solution for Tower of Hanoi C++ 949 views
  • TutorialsPoint Offline Version Download 2017 [Full Website] 877 views
  • Program to implement Binary Search Tree C++ 819 views
  • Program to implement RSA algorithm in C 810 views
  • Program to find LCM and HCF of 3 numbers in C++ 750 views
  • Program to convert Decimal to Hexadecimal C++ 704 views

© 2017 ProProgramming
 Privacy Policy About Contact Us