-----------------------------------

mathews411

Sat Jul 05, 2014 11:57 am


Big O Notation :|

-----------------------------------

So I'm taking a summer computer science class this year, and the topic of Big O notation has surfaced. In class it seemed fairly basic, we looked at simple equations (Ex. 8log n + 7n), the answer would be O(n) as it is the term that grows the fastest. That's stuff i can do.

Now we were given an assignment of similar type questions, but they threw something in that caused me to doubt what I know. Usually, when we would encounter a log, it would simple just be log(n), now they included log(n^2), or any kind of number for the exponent. 

For example I'll give a similar question that was in my assignment so if anyone can answer it they not doing my assignment for me.
3log(n^9) + 2nlog(n >2). 

Me and a friend both assumed the answer is O(nlogn), as nlogn grows faster then log(n). But then we started to talk about if it might be O(n^k) from the n^9 :think:.

In class, we never talked about how if a term is in a logarithm if it grows the fastest, or if it defaults to the original log and becomes a slower growth function.

Any help will be greatly appreciated, as Big O notation makes me die a little on the inside.

Hope I dint make this post to confusing!  :wall:


-----------------------------------

Dreadnought

Sat Jul 05, 2014 12:57 pm


Re: Big O Notation :|

-----------------------------------

Remember that you have
[code]log(n^k) = k*log(n)[/code]
With that in mind you should be able to compare the behavior of log(n^k) with n*log(n).


-----------------------------------

rdrake

Sat Jul 05, 2014 1:08 pm


Re: Big O Notation :|

-----------------------------------

If you expand out http://quicklatex.com/cache3/ql_e9ab29054fe9c6ad325d7754dbcc377f_l3.png out, you get http://quicklatex.com/cache3/ql_4375ad7fdf20c24c53adcc853c625e51_l3.png.

Recall from the logarithmic rules that

http://quicklatex.com/cache3/ql_723dbc4dc5e26407c37cab4a9e7f0221_l3.png

where http://quicklatex.com/cache3/ql_b954260098f5990f64022ae817bc3ea1_l3.png, so we get:

http://quicklatex.com/cache3/ql_080d623d34031ff49b6739c951241fb8_l3.png

So http://quicklatex.com/cache3/ql_792e35802caebf0769f8ca5f7216a70b_l3.png

Or you can be a jerk and say it's http://quicklatex.com/cache3/ql_e441f48dc05a25d39d0d1656716faa10_l3.png which it technically is.