Sorting nlog(sqrt(n))

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












A researcher claimed that she discovered a comparison-based sorting algorithm that runs in $O(nlog(sqrtn))$. Given the existence of an $Omega(nlog(n))$ lowerbound for sorting, how can this be possible?



Hint: It is possible. Don't waste time trying to disprove it. Just show why it is possible.






algorithms







share|cite|improve this question









New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.















  • 1




    $n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
    – Gokul
    3 hours ago















up vote
1
down vote

favorite












A researcher claimed that she discovered a comparison-based sorting algorithm that runs in $O(nlog(sqrtn))$. Given the existence of an $Omega(nlog(n))$ lowerbound for sorting, how can this be possible?



Hint: It is possible. Don't waste time trying to disprove it. Just show why it is possible.






algorithms







share|cite|improve this question









New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.















  • 1




    $n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
    – Gokul
    3 hours ago













up vote
1
down vote

favorite









up vote
1
down vote

favorite











A researcher claimed that she discovered a comparison-based sorting algorithm that runs in $O(nlog(sqrtn))$. Given the existence of an $Omega(nlog(n))$ lowerbound for sorting, how can this be possible?



Hint: It is possible. Don't waste time trying to disprove it. Just show why it is possible.






algorithms







share|cite|improve this question









New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











A researcher claimed that she discovered a comparison-based sorting algorithm that runs in $O(nlog(sqrtn))$. Given the existence of an $Omega(nlog(n))$ lowerbound for sorting, how can this be possible?



Hint: It is possible. Don't waste time trying to disprove it. Just show why it is possible.






algorithms




algorithms






share|cite|improve this question









New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 3 hours ago









Thinh D. Nguyen

3,45111468




3,45111468






New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 3 hours ago









confucius_did_shrooms

61




61




New contributor




confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






confucius_did_shrooms is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







  • 1




    $n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
    – Gokul
    3 hours ago













  • 1




    $n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
    – Gokul
    3 hours ago








1




1




$n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
– Gokul
3 hours ago





$n , logsqrtn = frac12n , log(n)= Omega(n ,logn)$. There's only a constant factor difference.
– Gokul
3 hours ago











1 Answer
1






active

oldest

votes

















up vote
3
down vote













As a set of functions $mathbbNlongrightarrowmathbbN$, $O(nlog(sqrtn))=O(nlog(n))$.






share|cite|improve this answer




















    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "419"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );






    confucius_did_shrooms is a new contributor. Be nice, and check out our Code of Conduct.









     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99307%2fsorting-nlogsqrtn%23new-answer', 'question_page');

    );

    Post as a guest

















    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    3
    down vote













    As a set of functions $mathbbNlongrightarrowmathbbN$, $O(nlog(sqrtn))=O(nlog(n))$.






    share|cite|improve this answer
























      up vote
      3
      down vote













      As a set of functions $mathbbNlongrightarrowmathbbN$, $O(nlog(sqrtn))=O(nlog(n))$.






      share|cite|improve this answer






















        up vote
        3
        down vote










        up vote
        3
        down vote









        As a set of functions $mathbbNlongrightarrowmathbbN$, $O(nlog(sqrtn))=O(nlog(n))$.






        share|cite|improve this answer












        As a set of functions $mathbbNlongrightarrowmathbbN$, $O(nlog(sqrtn))=O(nlog(n))$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 3 hours ago









        Thinh D. Nguyen

        3,45111468




        3,45111468




















            confucius_did_shrooms is a new contributor. Be nice, and check out our Code of Conduct.









             

            draft saved


            draft discarded


















            confucius_did_shrooms is a new contributor. Be nice, and check out our Code of Conduct.












            confucius_did_shrooms is a new contributor. Be nice, and check out our Code of Conduct.











            confucius_did_shrooms is a new contributor. Be nice, and check out our Code of Conduct.













             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99307%2fsorting-nlogsqrtn%23new-answer', 'question_page');

            );

            Post as a guest
































































            -

            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Image
            Clash Royale CLAN TAG #URR8PPP up vote 1 down vote favorite I'm using WordPress 4.9.8, CiviCRM to 5.5.1, I usually send email to contact by Search> Find contacts View contact details Action> Send email Send email ok, Contact received mail ok like picture But status only Email sent though contact read email or not. So, can CiviCRM can change status to Email read when contact read email? wordpress email share | improve this question asked Sep 26 at 0:12 ToanLuong 49 9 add a comment  |  up vote 1 down vote favorite I'm using WordPress 4.9.8, CiviCRM to 5.5.1, I usually send email to contact by Search> Find contacts View contact details Action> Send email Send email ok, Contact received mail ok like picture But status only Email sent though contact read email or not. So, can CiviCRM can change status to Email read when contact read email? wordpress email share | improve this questi...
            Read more

            Christian Cage

            Image
            Christian Cage Christian in March 2015 Birth name William Jason Reso Born ( 1973-11-30 ) November 30, 1973 (age 45) Kitchener, Ontario, Canada Residence Tampa, Florida, United States Spouse(s) Denise Hartmann ( m.   2001 ) Children 1 Professional wrestling career Ring name(s) Christian [1] Christian Cage [2] Conquistador Dos [3] Male Nurse [4] Billed height 6 ft 1 in (1.85 m) [1] Billed weight 212 lb (96 kg) [1] Billed from Tampa, Florida (WM18, TNA) Toronto, Ontario, Canada [1] Trained by Dory Funk Jr. [2] Ron Hutchison [5] Debut 1995 [5] Retired 2014 [6] William Jason Reso (born November 30, 1973) is a Canadian actor, podcaster and retired professional wrestler best known for his time in WWE under the ring name Christian , a shortened version of his original ring name Christian Cage that was also used during his tenure in Total Nonstop Action Wrestling (TNA). Reso was trained by former professional wrestlers Ron Hutchison and Dory Funk Jr. and m...
            Read more

            How to properly install USB display driver for Fresco Logic FL2000DX on Ubuntu?

            Image
            Clash Royale CLAN TAG #URR8PPP up vote 4 down vote favorite 1 I need to connect additional monitors on my computer and I get Fresco Logic FL2000DX USB display adapters. This adapters works perfect on Windows but I need to use on my development machine based on Ubuntu 16.04. I find this on git hub: https://github.com/fresco-fl2000/fl2000 and try to install it but installation fail. Can anyone help me regarding this? Thanks! ubuntu drivers display-settings proprietary-drivers share | improve this question asked Aug 16 '17 at 16:42 Ivijan Stefan Stipić 142 1 6 add a comment  |  up vote 4 down vote favorite 1 I need to connect additional monitors on my computer and I get Fresco Logic FL2000DX USB display adapters. This adapters works perfect on Windows but I need to use on my development machine based on Ubuntu 16.04. I find this on git hub: https://github.com/fresco-fl2000/fl2000 and ...
            Read more