0

I'm currently reading up on running times for algorithms. I understand the different terms of Big O, Theta and Omega... Lower, upper etc bounding...

However I have some assignments which requires me to list the Theta times. An example could be log(n)+n*sqrt(n)

In general one could just set the upper bound, but that's not the Theta bounding. How on earth do you find the theta bounding of a function?

Until now I've just basically applied the big O bounding as the theta bound. However I'm concerned that this isn't correct at all.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
SNAPSEHAMZ
  • 1
  • 1
  • Just calculate upper and lower bounds separately. Sandwich them closely enough. For example `n * sqrt(n) < log(n) + n * sqrt(n) < 2n * sqrt(n)`. – btilly Mar 30 '20 at 14:10

1 Answers1

1

In your example, this is Theta(n*sqrt(n)).

Why?

  1. This is O(n*sqrt(n)) because lim [n->inf] n*sqrt(n)+logn]/n*sqrt(n) < infinity
  2. This is Omega(n*sqrt(n)) because lim [n->inf] n*sqrt(n) + logn / n*sqrt(n) > 0.

This means, n*sqrt(n) gives us both asymptotic lower bound (Omega) and asymptotic upper bound (O) - and thus is also Theta.

More info in: What exactly does big Ө notation represent?

amit
  • 175,853
  • 27
  • 231
  • 333