Computer Science Canada

Big O Notation :|

Author:  mathews411 [ Sat Jul 05, 2014 11:57 am ]
Post subject:  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 Thinking.

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! Hit Wall

Author:  Dreadnought [ Sat Jul 05, 2014 12:57 pm ]
Post subject:  Re: Big O Notation :|

Remember that you have
code:
log(n^k) = k*log(n)

With that in mind you should be able to compare the behavior of log(n^k) with n*log(n).

Author:  rdrake [ Sat Jul 05, 2014 1:08 pm ]
Post subject:  Re: Big O Notation :|

If you expand out Posted Image, might have been reduced in size. Click Image to view fullscreen. out, you get Posted Image, might have been reduced in size. Click Image to view fullscreen..

Recall from the logarithmic rules that

Posted Image, might have been reduced in size. Click Image to view fullscreen.

where Posted Image, might have been reduced in size. Click Image to view fullscreen., so we get:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

So Posted Image, might have been reduced in size. Click Image to view fullscreen.

Or you can be a jerk and say it's Posted Image, might have been reduced in size. Click Image to view fullscreen. which it technically is.


: