Computer science proving big-O definition

In summary, the first question asks if f(n) = 100n^2 + 5n + 10 is in big-O of g(n) = n^3 - 100n^2. The second question is about how to prove this. If f is in big-O of g then |f - g| in big-O g. Intuitively, g(n) grows faster than f(n), right? Can you think of any algebraic way to capture this notion? As for the other question, how far have you gotten in your attempt? Have you at least written down what you're assuming and what you're trying to prove?
  • #1
KataKoniK
1,347
0
I have two questions here.
I must prove that [tex]f(n) = 100n^2 + 5n + 10[/tex] is in big-O of [tex]g(n) = n^3 - 100n^2[/tex]
I already found a constant [tex]c[/tex] and an [tex]n[/tex] that satisfies the condition such that [tex]f(n) \leq c * g(n)[/tex]. Let [tex]c = 1[/tex] and [tex]n = 201[/tex].
However, I am stuck on showing/manipulating the algebra that this is true.

Second question:

How would you prove this? I know you use the triangle inequality, but I have no idea how to implement this. Any help would be great, thanks.

If [tex]f[/tex] in big-O of [tex]g[/tex] then [tex]|f - g|[/tex] in big-O [tex]g[/tex]
 
Last edited:
Physics news on Phys.org
  • #2
I assume you meant to say that c=1 and n=201 satisfy the condition that

[tex]\forall m \geq n: f(m) < c * g(m)[/tex]

Intuitively, g(n) grows faster than f(n), right? Can you think of any algebraic way to capture this notion?



As for the other question, how far have you gotten in your attempt? Have you at least written down what you're assuming and what you're trying to prove?
 
  • #3
Hmm, I couldn't really think of an algebraic way of capturing that, but what I did was find the derivative of f and g. Then I solved for [tex]g'(n) - f'(n) = 0[/tex] and got n = 133.3 and -0.12. However, I do not know how to better show that f is less than c * g(n) for n >= 210.


btw, I solved the |f - g| is in big-O of g
 
  • #4
I couldn't really think of an algebraic way of capturing that,
I bet you have, and just haven't realized it yet.

Why did you solve g'(n) - f'(n) = 0 for n?
 
  • #5
Whoops, I meant that I solved for (f - g)' because we want to know when the function is >= 0 and not less than 0. Am I doing the right thing?
 
  • #6
Probably. But if you said what you're trying to do, it might help you organize it into a proof.
 
  • #7
Alright, I will give that a try, thanks.
 

1. What is the Big-O notation in computer science?

The Big-O notation is a mathematical notation used to describe the complexity or runtime of an algorithm. It represents the worst-case scenario of how long an algorithm will take to run as the input size grows.

2. How is the Big-O notation useful in computer science?

The Big-O notation allows us to analyze and compare the efficiency of different algorithms. It helps us determine which algorithm is more suitable for a given problem based on its runtime complexity.

3. What is the difference between O(1) and O(n) in Big-O notation?

O(1) denotes constant time complexity, meaning the algorithm will take the same amount of time to run regardless of the input size. O(n), on the other hand, represents linear time complexity, where the runtime increases in proportion to the input size.

4. Can you give an example of an algorithm with O(n^2) time complexity?

A common example of an algorithm with O(n^2) time complexity is the nested loop algorithm, where the input is iterated through twice. The runtime will increase quadratically as the input size grows.

5. How do you prove that an algorithm has a certain Big-O complexity?

To prove the Big-O complexity of an algorithm, you need to show that the algorithm's runtime grows at the same rate or slower than the Big-O notation. This can be done by analyzing the algorithm's code and identifying the operations that contribute to its runtime, then evaluating their complexity and combining them to get the overall complexity.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
2
Views
812
  • Calculus and Beyond Homework Help
Replies
1
Views
450
  • Calculus and Beyond Homework Help
Replies
7
Views
675
  • Calculus and Beyond Homework Help
Replies
3
Views
465
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
13
Views
899
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
732
Back
Top