So, we have to write a C program that creates and traverses the singly linked list. Take care while handling the pointers in the program, because there are a lot of pointer movements. Also read: Singly Linked List Declaring a Singly Linked List: So, we know that we can declare…
Category: Infinity Fitness
Everything you need to know about building muscles and maintaining a great overall health
A singly linked list consists of elements that are called ‘nodes’. Every element contains data and a link to the next element in the linked list. Singly linked list contains a number of elements that are linked sequentially with the help of pointers. These elements or nodes are generally self…
Linked list is a linear data structure like array. In array data structure, elements are stored in contiguous memory location but in linked list data structure, elements are not necessarily stored in contiguous memory location. The elements in the linked list are connected with pointers. Array v/s Liked List: Array…
Master Theorem:
Master Theorem is a cookbook method for determining solutions to recurrence equations of a specific form.
So, in the first step you should match your recurrence equation with the equation given below and determine the value of some constants (a,b,k and p) then select the appropriate case-
T(n) = a T(n/b) + Θ(nk logpn)
Where a≥1, b>1, k≥0 and p∈R(real numbers). These conditions are important. Why? Because these condition help to check the properties the given constants (a, b, k, p). That helps to determine the time complexity using Master theorem.
CASE-1: if a > bk , then T(n)=Θ(nlogba)
CASE-2: if a = bk ,
a) If p>-1, then T(n)=Θ(nlogba logp+1n)
b) If p=-1, then T(n)=Θ(nlogba log(logn))
c) If p<-1, then T(n)=Θ(nlogba)
CASE-3: if a < bk ,
a) If p≥0, then T(n)=Θ(nklogpn)
b) If p<0, then T(n)=O(nk)
For,
Substitution Method click here!
Recursion tree method click here!
Example-1: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + n2
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=2, p=0
Now, identifying the matching case-
a = bk
Why?
a = bk => 4 = 22 => 4 = 4
and
p>-1
Why?
Because, p=0
Hence, CASE 2.a is applied here!
T(n) = Θ(nlogba logp+1n)
T(n) = Θ(nlog24 log0+1n)
T(n) = Θ(n2.logn)
Example-2: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + nlogn
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=1, p=1
Now, identifying the matching case-
a > bk
Why?
a > bk => 4 > 21 => 4 > 2
Hence, CASE 1 is applied here!
T(n) = Θ(nlogba)
T(n) = Θ(nlog24)
T(n) = Θ(n2)
Example-3: Solve the given recurrence using Master theorem-
T(n) = 5T(n/3) + n
Simply, compared with the above equation given in the Master theorem.
Hence,
a=5, b=3, k=1, p=0
Now, identifying the matching case-
a > bk
Why?
a > bk => 5 > 31 => 5 > 3
Hence, CASE 1 is applied here!
T(n) = Θ(nlogba)
T(n) = Θ(nlog35)
Example-4: Solve the given recurrence using Master theorem-
T(n) = 4T(n/2) + n3
Simply, compared with the above equation given in the Master theorem.
Hence,
a=4, b=2, k=3, p=0
Now, identifying the matching case-
a < bk
Why?
a < bk => 4 < 23 => 4 < 8
and
p≥0
Why?
Because, p=0
Hence, CASE 3.a is applied here!
T(n) = Θ(n3log0n)
T(n) = Θ(n3)
Example-5: Solve the given recurrence using Master theorem-
T(n) = 3n T(n/2) + nn
Here, values of a and k are not constant, so the Master theorem cannot apply here.
As, a=3n , b=2 , k=n, p=0
Example-6: Solve the given recurrence using Master theorem-
T(n) = 2T(n/4) + n0.55
Simply, compared with the above equation given in the Master theorem.
Hence,
a=2, b=4, k=0.55, p=0
Now, identifying the matching case-
a < bk
Why?
a < bk => 2 < 40.55 => 40.50 < 40.55
and
p≥0
Why?
Because, p=0
Hence, CASE 3.a is applied here!
T(n) = Θ(n0.55log0n)
T(n) = Θ(n0.55)
Circular Linked list is a sequence of nodes in which every node connects to its next node in the sequence, by the pointer. The last node also connects to the first node in the sequence. Hence a circular linked list is similar to the singly linked list with an extra…
Circular doubly linked list is a mixture or combination of doubly linked list and circular linked list. In a circular doubly linked list two successive nodes are linked by previous pointer and next pointer. The first node points to the last node by the previous pointer and the last node…
In C language when a structure is referring or pointing to the structure of the same type, then it is called ‘self referential structure’. Example of a structure- Example of a self referential structure- Here, *link is a pointer to the structure of type ‘manu’. Hence, it is a self…
Dynamic Memory Allocation: When we need to change the size of data structure at runtime, then we use dynamic memory allocation. C language provides some functions for dynamic memory allocation. There are 4 library functions in C language that are defined under the ‘stdlib.h’ header file to facilitate dynamic memory…
Recursion Tree Method (Iteration Method):
Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost of a single problem.
Example 1– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = 2T(n/2) + n
Explanation:
In the above diagram, the recurrence relation divide into two sub problems. Understood? If not, then look at the recursive equation and diagram simultaneously. The diagram showing the actual meaning of the equation.
Again,
Now again,
T(n) = n + n + n + …. + (log2n times)
Why log2n times? Because the height of the tree is log2n.
T(n) = n*log2n
T(n) = O(nlog2n)
Example 2– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = 2T(n/2) + c; n>1
T(n) = c; n=1
Explanation:
Similarly as previous question-
T(n) = c + 2c + 4c + 8c + … + (log2n times)
T(n) = c[ 1 + 2 + 4 + 8 + … + (log2n times)]
Simply solve the G.P. inside the brackets.
T(n) = c[2log2n – 1] [2log2n = nlog22 = n]
T(n) = c[n – 1]
T(n) = O(n)
Example 3– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = T(n/3) + T(2n/3) + n
Explanation:
This question is somewhat different from above question. Why?
Because, in this question, the recurrence relation is divided into two different parts. In the above questions, the recurrence relation is divided into two equal parts.
Let’s see how to solve this one-
It is clear that the height of the tree is not balanced here. The height of the leftmost branch of the tree is log3n and the height of the rightmost branch of the tree is log3/2n.
So, the longest path is rightmost one, and its length is log3/2n.
Hence,
T(n) = n + n + n + …. + (log3/2n times)
Why log3/2n times? Because the height of the rightmost tree is log3/2n.
T(n) = n*log3/2n
T(n) = O(nlog3/2n)
Recurrence Relation: A recurrence relation is a equation or inequality that express a function in terms of its value on a smaller input. How to solve these recurrences? any idea? So, there are three ways to solve the recurrence relations. 1. Substitution Method 2. Recursion Tree Method (Iteration Method) 3.…