Answer the following questions using the simplest possible Θ (Theta) notation.
Question:
Answer the following questions using the simplest possible Θ (Theta) notation. Assume as usual that f(n) is Θ(1) for constant values of n.
a) Solution to the recurrence T(n)=T(n-1)+2?
b) Expected number of nodes in a skip list storing n items?
c) Solution to the recurrence T(n)=4T(n/4)+n?
d) Solution to the recurrence: f(n)=2f(n-1)-f(n-2)+1.
e) Time to determine if a graph with n nodes and m edges has a 5-clique?
Summary:
In this question, we have to answer the questions related to theta asymptotic notation.
Explanation:
Asymptotic notation:
The best algorithm to solve a problem is by checking the efficiency of the algorithm. This is performed by computing the time complexity of the algorithm. Asymptotic notations are shorthand representations of time complexity, which is represented as the fastest possible or slowest possible or average possible.
Asymptotic notations indicate the order of growth of the functions, which indicate the algorithm efficiencies are:
- Big oh notation.
- Omega notation.
- Theta notation.
θ (Theta) notation:
This notation defines running time as a function between upper bound and lower bound. We have to answer the following questions given below:
(a) T(n)= T(n-1)+2
(b) In skip list sorting, the idea is to divide the numbers into multiple layers, so that while searching, it can skip those numbers which are not in the range on layer 1. The space complexity of skip list sort with n items is O(n log n).
(c)T(n)=4T(n/4)+n
n+n+n+n…………..=n times.
Time complexity=θ(n2).
(d)f(n)=2f(n-1)-f(n-2)+1
1+3+9+….+n=3n.
Time complexity = θ(3n).
(e) A subgraph in the graph can be determined by the clique problem. In a tree with n vertex and m edges, to determine 5-clique the time complexity required is O(nkk2).
Where k is 5, so we get O(25 n5) = O(n5).
Because it has to go through n5 subgraphs and check for 52 (25) edges.
Also, read Dijkstra’s algorithm to find the shortest path.
