Q1 – Consider the following functions:
f(n) = 3n√n
g(n) = 2Гn log2n
h(n) = n!
Which of the following is true?
h(n) is O(f(n))
h(n) is O(g(n))
g(n) is not O(f(n))
f(n) is O(g(n))
(UGC NET DEC 2023)
Ans – (2, 3, 4)
Explanation – In g(n), there is gamma function (Гn).
Гn = ∫0infinity xn-1 e-x dx = (n-1)!
Then f(n) = 3*n√n, So, its complexity will be n√n.
g(n) = 2Гn log2n, So, its complexity will be 2(n-1)! log2n.
h(n) = n!
we know that n! > n√n, because
if n = 1, n! > n√n à 1 = 1
If n = 16, then 16! > 164 => 2*1013 > 65536
This means that f(n) < h(n) < g(n)
Option 2, 3 and 4 are correct.
Note – I copied the original question in the original paper of ugc net. But in the g(n), different authors used √ function instead of Г function. If √n is there, the g(n) will have same complexity as f(n), so in this way option 4 will be correct.
Q2 – 2-3-4 trees are B-trees of order 4. They are isometric of _________ trees.
AVL
AA
2-3
Red-Black
(UGC NET DEC 2023)
Ans – (4)
Explanation – A 2-3-4 tree is a self-balancing multi-way search tree in which a node can have 2, 3, or 4 children’s nodes and have 1, 2, or 3 keys. They are a special case of B-Trees (B-tree of order 4).
2-3-4 trees are basically isometric to Red-Black trees, meaning they describe the same data structure but in different forms.
A 2-node becomes a black node in a red-black tree.
A 3-node becomes a black node with one red child.
A 4-node becomes a black node with two red children.
Q3 – Which of the following is TRUE?
The cost of searching an AVL tree is ϴ (log n) but that of binary search is 0(n)
The cost of searching an AVL tree in ϴ (log n) but that of complete binary tree is ϴ(n log n)
The cost of searching a binary tree is 0(log n) but that of AVL tree is ϴ (n)
The cost of searching an AVL tree is ϴ (n log n) but that of binary search tree is 0(n)
(UGC NET DEC 2023)
Ans – (1)
Explanation – Complexity of Search of AVL Trees is ϴ(log n)
An AVL tree is a self-balancing binary search tree (BST). The height of an AVL tree stays logarithmic (O(log n)) in the worst-case scenario. Naturally, searching in an AVL tree will have a time complexity of ϴ(log n).
Complexity of Searching in a Binary Search Tree in the worst case, the time becomes O(n).
A normal binary search tree (BST) may turn into an unbalanced one, and as such, if the tree is skewed, the time taken to search becomes O(n) in the worst case. This happens when all elements are inserted in sorted order, and it turns the tree into a linked list.
