It is asking for asymptotic complexity

So, maximum of all 3 operation is nlogn

So, O(nlogn) or O(n^{2}) fine for answer

The Gateway to Computer Science Excellence

+1 vote

Here In this question it is given that we have to perform nlogn decrease key operation and n find operation .

1)Finding an element in the linked list itself takes O(n) and** there are N such operations total=O(n ^{2}).**

2)Decrease key: Find key O(n) + O(1) for decrease=O(n) and

Please correct Me :

Image :

+1 vote

Linked List

i. root(n) insert operations = $O(root(n))$ we can insert at the beginning of the linked list.

ii. O(nlogn) decrease key operation = as it's not given that linked is sorted, Hence, O(1) needs for one decrease key operation, total T.C needed is $O(nlogn)$.

iii. n find operations, each needs O(n), total cost $O(n^2)$

Max if these three is $O(n^2)$.

**Hence, correct answer is (B).**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,385 answers

198,557 comments

105,368 users