algorithm - How to determine the runtime of this function -

i'm having trouble basic runtime understanding, maybe can clarify me. how go determining runtime of function?

i need determine rather f = o(g) or f = omega(g) or f = theta(g)

f(n) = 100n + logn
g(n) = n + (logn)²

so 100n , n in same order; , linear time > log time; @ point still need @ log part? or can determine f = theta(g)?

you can safely determine same order of magnitude. there no need @ "log part".

here formal proof specific case, general proof can shown limit arithmetic.

let's @ function h(n) = f(n)/g(n) n approaches infinity, if stays bounded above 0 , below number m know f(x) = theta(g(x)) (because of how theta defined).

so have h(n) = (100n + logn)/(n + logn^2)

we know if show for real x, holds natural numbers too. enough show for:

h(x) = (100x + logx)/(x + logx^2)

we know l'hospital's rule if derivatives of nominator , denominator exist , converge limit of original function exists , equals same number too. let's apply , get:

lim x-> infinity , h(x) = (100x + logx)/(x + logx^2) =   lim x-> infinity , (100+1/x) / (1 + (2log(x) / x) )  

we know 1/x approaches 0 x approaches infinity, , (2logx)/x approaches 0 x approaches infinity (in words (time > log time)). limit arithmetic

lim x-> infinity h(x) = 100/1 = 100

since limit exists in r , nonzero f(x) = theta(g(x)) wanted show.