Member Avatar for hibzgums

my instructor told me to report the big theta notation and i don't know anything about it!!! sorry but i'm a real noob at it... T_T please help...
he was asking about its history. and all i called find was the formula. this is really bad. T_T
aside from that, i can't find anything about it.

  • 2 Contributors
  • 2 Replies
  • 72 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by hibzgums

Dani AI

Generated

Quick primer for (and thanks to for the Big-O pointer).

Theta notation gives a tight asymptotic bound. Formally: f(n) is Theta(g(n)) if there exist positive constants c1, c2 and n0 such that for all n >= n0:
c1 * g(n) <= f(n) <= c2 * g(n).
Intuition: f grows like g up to constant factors — neither much faster nor much slower.

Example and how to prove it quickly: take f(n) = 3n^2 + 2n + 1. For n >= 1 we have 3n^2 <= f(n) <= 6n^2, so choose c1 = 3, c2 = 6, n0 = 1. That shows f(n) is Theta(n^2). The usual proof pattern is: pick a candidate g(n) (often the highest-degree term for polynomials), find a c2 for the upper bound and a c1 for the lower bound, and give an n0 that makes both inequalities hold.

Quick cautions: Theta requires both upper and lower bounds; if you can only show one side, use O (upper) or Omega (lower) instead. All bounds are asymptotic — constant factors and lower-order terms are ignored for large n. If your instructor asked for history, mention that asymptotic notation has roots in analytic number theory and was standardized in algorithm literature (see classic algorithm texts for citations).

Recommended Answers

All 2 Replies

Member Avatar for hibzgums

i don't think so because one group's assigned to that one... sorry for the late reply... T_T

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.