Order of f(n) and g(n): O(n^4) and O(n^2)

  • Thread starter Gear2d
  • Start date
In summary, the order of the two functions f(n) = (log(n^3))^4 and g(n) = (log(n^7))^2 can be determined by breaking them down into their individual components and applying the Big Oh rules for logarithmic functions. Based on this, f(n) has an order of O(n^4) and g(n) has an order of O(n^2).
  • #1
Gear2d
51
0

Homework Statement



What is the order of the two functions:

f(n) = (log(n^3))^4
g(n) = (log(n^7))^2

Homework Equations



http://www.augustana.ca/~hackw/csc210/exhibit/chap04/bigOhRules.html

The Attempt at a Solution



f(n) = (log(n^3))^4 = log(n^3) * log(n^3) * log(n^3) * log(n^3)

g(n) = (log(n^7))^2 = log(n^7) * log(n^7)

Based on the Big Oh rules (the link above) using Log of a Power Rule we see that for one log(n^3) and one log(n^7) the order is O(log n) and O(log n). Now since f(n) is raised to power of 4 the order is now O(log n)^4 and g(n) is raised to power of 2 so O(log n)^2.

Now using Comparison Rule 2 we that f(n) is O(n^4) and g(n) is O(n^2).

Would this reasoning be correct?
 
Last edited:
Physics news on Phys.org
  • #2
I'm not sure how you used comparison rule 2 to get that. Everything up until there is fine though.
 

1. What does "O(n^4)" mean in the context of the order of f(n) and g(n)?

"O(n^4)" is a notation used in computer science and mathematics to describe the upper bound of a function's growth rate. In this context, it means that the function in question (f(n) or g(n)) will not grow at a rate faster than n^4. This can also be interpreted as the function having a time complexity of O(n^4).

2. How does "O(n^4)" compare to "O(n^2)" in terms of function order?

In terms of function order, "O(n^4)" is a higher order than "O(n^2)". This means that the function with a time complexity of O(n^4) will have a slower growth rate than the function with a time complexity of O(n^2). In other words, as n approaches infinity, the function with O(n^4) will take longer to run than the function with O(n^2).

3. Can a function have a time complexity of both O(n^4) and O(n^2)?

No, a function can only have one time complexity. The notation "O(n^4)" and "O(n^2)" are used to indicate the upper bound of a function's growth rate, meaning that the function will not grow at a rate faster than n^4 or n^2. It is possible for a function to have a time complexity of O(n^4) and a space complexity of O(n^2), but not both time complexities simultaneously.

4. How does the order of f(n) and g(n) affect algorithm efficiency?

The order of f(n) and g(n) can greatly affect the efficiency of an algorithm. Generally, the lower the order, the more efficient the algorithm will be. In the case of "O(n^4)" and "O(n^2)", the algorithm with a time complexity of O(n^2) will be more efficient than the one with O(n^4) as the input size grows larger. This is because the algorithm with O(n^2) will take less time to compute compared to the one with O(n^4).

5. Can the order of f(n) and g(n) change depending on the input size?

Yes, the order of f(n) and g(n) can change depending on the input size. For example, an algorithm with a time complexity of O(n^4) may have a lower order for small input sizes, but as the input size increases, the order may change to O(n^2). This is because the notation "O(n^4)" and "O(n^2)" only describe the upper bound of a function's growth rate, and the actual order may vary depending on the input size.

Similar threads

Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
    • Calculus and Beyond Homework Help
Replies
3
Views
544
How to show that these sequences are summable?
    • Calculus and Beyond Homework Help
Replies
1
Views
249
Limits and integration problem
    • Calculus and Beyond Homework Help
Replies
4
Views
802
Fourier series of this scale and shift of triangle wave
    • Calculus and Beyond Homework Help
Replies
1
Views
202
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
499
Prove that ## \sum_{n\leq x}\frac{\phi(n)}{\sqrt{n}}=Cx^{3/2}+.... ##.
    • Precalculus Mathematics Homework Help
Replies
4
Views
971
Prove that ## g(x)=f(x)\log {x}-\int_{2}^{x}t^{-1}f(t)dt ##.
    • Precalculus Mathematics Homework Help
Replies
7
Views
816
The only prime of the form n^2-4 is 5?
    • Calculus and Beyond Homework Help
Replies
2
Views
2K
Proving that ##\lim [\sqrt{4n^2 +n} - 2n] = \frac{1}{4}##
    • Calculus and Beyond Homework Help
Replies
9
Views
1K
How to convince myself that I can take n=1 here?
    • Calculus and Beyond Homework Help
Replies
1
Views
597

Hot Threads

Recent Insights

Back
Top