Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Big O Notation :|
Author Message
mathews411

Posted: 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 .

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!

Posted: 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).
rdrake

Posted: Sat Jul 05, 2014 1:08 pm   Post subject: Re: Big O Notation :|

If you expand out out, you get .

Recall from the logarithmic rules that

where , so we get:

So

Or you can be a jerk and say it's which it technically is.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 3 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: