How to evaluate square of logarithms to solve s(n) = O(a(n))?I've never used log before, nor worked with big-O notation, so I'm completely useless at this stuff. Any, any, any help or direction you can give would be helpful as the professor hasn't covered this in the least and this is the type of thing he's throwing at us on exams:Find a(n) where s(n) = O(a(n)) for: s ( n ) = ( n log 2 ⁡ n + 1 ) 2 I just have no idea where to even begin.By way of apology / context, I've read my discrete math text book chapter on log and big-O notation 8-10 times now, scoured Google for a full day, banged my head against this for hours more and come up with nothing. I don't know how but I'm in my 4th year of college and somehow none of my classes covered logarithms and I'm just not finding good resources on how to learn this stuff, so here I am for help. (I've given up on passing the class already, just trying to keep learning so I can hopefully pass when I retake next semester.)

Question

How to evaluate square of logarithms to solve s(n) = O(a(n))?I&#039;ve never used log before, nor worked with big-O notation, so I&#039;m completely useless at this stuff. Any, any, any help or direction you can give would be helpful as the professor hasn&#039;t covered this in the least and this is the type of thing he&#039;s throwing at us on exams:Find a(n) where s(n) = O(a(n)) for:  s  (  n  )  =  (  n      log    2    ⁡  n  +  1      )    2  I just have no idea where to even begin.By way of apology / context, I&#039;ve read my discrete math text book chapter on log and big-O notation 8-10 times now, scoured Google for a full day, banged my head against this for hours more and come up with nothing. I don&#039;t know how but I&#039;m in my 4th year of college and somehow none of my classes covered logarithms and I&#039;m just not finding good resources on how to learn this stuff, so here I am for help. (I&#039;ve given up on passing the class already, just trying to keep learning so I can hopefully pass when I retake next semester.)

Quinn Hansen · Accepted Answer

What you big-O does is just follow the biggest contribution that dominates over all others when   n is really large. And you ignore any constant prefactors that really don&#039;t matter. It just tells you in what way an expression grows.Just square this:      n    2    (      log    2    ⁡  n      )    2    +  2  n      log    2    ⁡  n  +  1You see that at least the   +  1 is completely irrelevant here.On the other hand: logarithm (any base, they are all proportional to one another via       log          a        ⁡  n  =            log      ⁡      n              log      ⁡      a       where   log can be a natural logarithm, or base-10, whatever you prefer) grows much more slowly than any power of   n does. So   O  (  1  )  &amp;lt;  O  (  log  ⁡  n  )  &amp;lt;  O  (  n  )  &amp;lt;  O  (  n  log  ⁡  n  )The middle term is negligible compared to the first one, so you can write  s  (  n  )  =  O  (      n    2    (  log  ⁡  n      )    2    )

How to evaluate square of logarithms to solve s(n) = O(a(n))?

Answered question

Answer & Explanation

New Questions in Algebra II