GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
32 views

Consider the following variation on merge sort for the large values of 'n  'instead of recursing until 'n' is sufficiently small recur atmost a constant 'r' times and then use insertion sort to solve the 2r resulting sub problems.What is the running time of this variation

a)theta(n)

b)theta(n log n)

c)theta(n2)

d)theta(log n)

asked ago in Algorithms by Boss (8.1k points) 1 14 99 | 32 views
Answer should be theta (n logn). I don't know how, but I read it once somewhere. And this is the way sort function is implemented in STL of C++

its given as theta (n2)

sorry I was wrong.

This may help you: http://gateoverflow.in/99455/sorting-algorithm

its not clear from that link

Can someone please help

@habib @arjun sir

Please log in or register to answer this question.



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
Top Users Oct 2017
  1. Arjun

    23396 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8158 Points

  4. srestha

    6286 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4344 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Great Question khushtak
Good Question Ishrat Jahan
Good Answer Arjun
Revival Arjun
Nice Question Kathleen
Nice Answer janakyMurthy
Renewal janakyMurthy
Renewal Bikram
Nice Answer Bikram
Ancestor Arijit 2
27,316 questions
35,169 answers
84,074 comments
33,262 users