Payton Rasmussen

2022-09-06

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{\mathrm{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.)

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{\mathrm{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.)

Quinn Hansen

Beginner2022-09-07Added 11 answers

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't matter. It just tells you in what way an expression grows.

Just square this:

${n}^{2}({\mathrm{log}}_{2}n{)}^{2}+2n{\mathrm{log}}_{2}n+1$

You 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 ${\mathrm{log}}_{a}n=\frac{\mathrm{log}n}{\mathrm{log}a}$ where $\mathrm{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)<O(\mathrm{log}n)<O(n)<O(n\mathrm{log}n)$

The middle term is negligible compared to the first one, so you can write

$s(n)=O({n}^{2}(\mathrm{log}n{)}^{2})$

Just square this:

${n}^{2}({\mathrm{log}}_{2}n{)}^{2}+2n{\mathrm{log}}_{2}n+1$

You 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 ${\mathrm{log}}_{a}n=\frac{\mathrm{log}n}{\mathrm{log}a}$ where $\mathrm{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)<O(\mathrm{log}n)<O(n)<O(n\mathrm{log}n)$

The middle term is negligible compared to the first one, so you can write

$s(n)=O({n}^{2}(\mathrm{log}n{)}^{2})$

$\frac{20b}{{\left(4{b}^{3}\right)}^{3}}$

Which operation could we perform in order to find the number of milliseconds in a year??

$60\cdot 60\cdot 24\cdot 7\cdot 365$ $1000\cdot 60\cdot 60\cdot 24\cdot 365$ $24\cdot 60\cdot 100\cdot 7\cdot 52$ $1000\cdot 60\cdot 24\cdot 7\cdot 52?$ Tell about the meaning of Sxx and Sxy in simple linear regression,, especially the meaning of those formulas

Is the number 7356 divisible by 12? Also find the remainder.

A) No

B) 0

C) Yes

D) 6What is a positive integer?

Determine the value of k if the remainder is 3 given $({x}^{3}+k{x}^{2}+x+5)\xf7(x+2)$

Is $41$ a prime number?

What is the square root of $98$?

Is the sum of two prime numbers is always even?

149600000000 is equal to

A)$1.496\times {10}^{11}$

B)$1.496\times {10}^{10}$

C)$1.496\times {10}^{12}$

D)$1.496\times {10}^{8}$Find the value of$\mathrm{log}1$ to the base $3$ ?

What is the square root of 3 divided by 2 .

write $\sqrt[5]{{\left(7x\right)}^{4}}$ as an equivalent expression using a fractional exponent.

simplify $\sqrt{125n}$

What is the square root of $\frac{144}{169}$