how to define theta notation nd show that 4n^2+3n is o(n^2)
nayna.kujur 0 Newbie Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Theta notation is basically the same as Big O notation except instead of an upper bound, it represents a tight bound (ie. upper and lower). More formally (where Theta is the tight bound, O is the upper bound, and Omega is the lower bound):
f(x) = Theta(g(x)) iff f(x) = Omega(g(x)) and f(x) = O(g(x))
In all cases for complexity, constant terms are discarded, and often all but the most significant remaining terms will also be discarded. In your example, 4 and 3n are insignificant compared to n^2, so they're discarded to produce o(n^2).
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.