Question

Big-O notation, how to find constants a and b? Any guide or video online?

I am not sure if I should post this in math or computer science. I am having trouble with big-o, omega, theta etc. But I want to work on them 1 by 1. I am having trouble finding guides or videos on how to find constants a and b. I kind of have an idea with a, but have a huge trouble for b :(

A lot of videos I have watched focused on the concept, but none that I saw explained how to find a and b. By finding I mean I need to know the number for a and b. It is for calculating algorithm running time.

Does anyone have a good guide on how to learn big-o?

Thanks!

Example problem:
Using the big-o definition (must specify two positive constants), prove that 4n^2 - 2n + 5 = O(n^2)

The a I found is 7. Which came from:

4n^2 - 2n + 5 <= 4n^2 -2n^2 + 5n^2 = 7n^2

But I don't know how to find constant b.

Answer 1

\(g=O(f)\) means
\[\lim_{x\to \infty}\frac{f}{g}=c\] where \(c\neq 0\) if \(c=1\) you say
\[g=o(f)\]

Answer 2

"finding the constants \(a\) and \(b\)" must be part of a specific problem

Answer 3

@satellite73, thanks for your quick response. I will find an example shortly and post it.

Answer 4

i still don't know what \(a\) and \(b\) mean in your definition, but there is a good example here
http://en.wikipedia.org/wiki/Big_O_notation

Answer 5

maybe your \(a\) corresponds to the \(x_0\) and this example and your \(b\) is their 13