extract first elements thats going to take 0(logn) than than repeat the same till 6 steps

you will get it in O(logn)

you will get it in O(logn)

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

closed as a duplicate of:
GATE2003-23

0

extract first elements thats going to take 0(logn) than than repeat the same till 6 steps

you will get it in O(logn)

you will get it in O(logn)

+1

0

guys some are taking out O(1) while some are taking out O(logn)

like in some lectures, we have O(logn) while, Kiran kumar pasupuleti sir has given we have O(1). so whats the orrect explaination

like in some lectures, we have O(logn) while, Kiran kumar pasupuleti sir has given we have O(1). so whats the orrect explaination

0

it can be solved for 0(1) as well as O(logn) it will depend upon the criteria which is :

1) O(1) if you can easily access elements of the heap. (comparison will be 2^k-1 where k=constant )

2) O(logn) if you can only access the first element of heap.

i think their answer must be different based on the idea of accessing elements of the heap.

1) O(1) if you can easily access elements of the heap. (comparison will be 2^k-1 where k=constant )

2) O(logn) if you can only access the first element of heap.

i think their answer must be different based on the idea of accessing elements of the heap.

0

it should be O(log n) because

min element will be root takes O(1).

2nd smallest will be at level 1(root is level 0)

3rd smallest element will be at 2nd or 3rd level

similarly 7th smallest element can be found in level 1 to level 6

now we can not do traversal in min-heap or max-heap so first have to delete smallest element then only 2nd smallest element can be found.

after each deletion we have to perform heapify operation which takes O(logn)

so for doing k operation we will require O(k*log n)=O(log n)

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,534 questions

54,122 answers

187,321 comments

71,040 users