The Gateway to Computer Science Excellence
+1 vote
172 views

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
0

It is asking for asymptotic complexity

So, maximum of all 3 operation is nlogn

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

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

maximum of 3 operation will be nlogn

right?
0
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
0
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)
0

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

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

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
198,557 comments
105,368 users