Reliance Jio is the biggest telecom operator in India. Google, Facebook, and other big tech firms invested in Reliance Jio recently. Google also announced a partnership with Jio to build the cheapest 5G Smartphone. Jio Phone Next powered by Google’s Android will be the cheapest 5G smartphone by Jio in…
Category: Infinity Fitness
Everything you need to know about building muscles and maintaining a great overall health
So, we have to write a C program that creates and traverses the circular doubly linked list in both direction i.e. in forward and backward direction. Take care while handling the pointers in the program, because we are going to handle lots of pointers. Also read: Circular Doubly Linked List…
So, we have to write a C program that creates and traverses the circular linked list. Take care while handling the pointers in the program, because we are going to manipulate lots of pointers. Also read: Circular Linked List Declaring a Circular Linked List: So, we know that we can…
So, we have to write a C program that creates and traverses the doubly linked list. Take care while handling the pointers in the program, because we are going to manipulate lots of pointers. Also read: Doubly Linked List Declaring the Doubly Linked List: So, we know that we can…
We know that, in a singly linked list every elements (node) has a pointer to its next element (node) in the sequence. Hence, if we want to traverse the singly linked list then we can traverse in only one direction. We cannot traverse back in the singly linked list. But…
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…
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)