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(n2).
2)Decrease key: Find key O(n) + O(1) for decrease=O(n) and there are nlogn such operations: total O(n2logn).
Please correct Me :
Image :

in Algorithms by Boss (11.9k points) | 172 views

It is asking for asymptotic complexity

So, maximum of all 3 operation is nlogn

So, O(nlogn) or O(n2) fine for answer

Didn`t get you how it is nlogn?
why not nlogn

maximum of 3 operation will be nlogn

What I absorbed from the given statement is :
On a set of n elements, we have Max sqrt{n} insert nlogn decrease key operations and O(n) Find key operations
a/c to me answer should be "C" - 1 decrease key will include 1 find(O(N)) + 1 decrease key  (O(1)) no additional info is givent that list is sorted so no need to arrange it. so for nlogn decrease key, it would be n^2( logN ) and till that time remaining operations will be completed.

1 Answer

+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).

by Boss (44.2k points)

manu for decrese key you need to search the list it will take O(n2logn)

@anu As per the definition of decrease key operation, pointer is always given to that node whose key needs to be decreased.
give any refference, from my side refference is every gate question, they said pointer is given

it's an implicit thing, decrease_key operation always meant to decrease the key of a node which will be passed as a parameter./
Anyway, I am sending you the  following decrease key procedure from Heap-sort patr from Coreman:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,368 users