0

i heard somewhere that for example to tell that a function has a big theta of n it has to have complexity of n in both its best and worst cases, so linear search would not be big theta of n because it has best case O(1), but i doubt this information, so if you have any code which you want to analyse, when to say that this code has a big theta of some function ?

Mohamed EL Tair
  • 357
  • 1
  • 13
  • This is wrong. Best case is irrelevant. – n. m. could be an AI Mar 22 '17 at 15:18
  • 1
    Big-theta is notation for *functions*, not algorithms. An algorithm has several functions of input size associated with it - best/average/worst time, best/average/worst size, acceleration (for parallel algorithms) and so forth. Each of them can be described in theta-notation. Best case usually isn't interesting. – Abstraction Mar 22 '17 at 15:21
  • 3
    Does this answer your question? [What is the difference between Θ(n) and O(n)?](https://stackoverflow.com/questions/471199/what-is-the-difference-between-%ce%98n-and-on) – Scratte Apr 20 '20 at 06:47

1 Answers1

0

To understand big theta, we should first review big O and big omega. Big O describes the worst case runtime of a function, which means that it will never perform worse than that. Big omega describes the best case runtime of a function, meaning the function will never perform better than that. Big theta is found when big O = big omega, because the worst case = the best case, so the function is bounded above and below by the same time complexity. For example, when doing matrix multiplication of 2 matrices, each with dimensions n x n, the runtime of the function is O(n^3). The runtime is also bigOmega(n^3). This is because in both the worst and best cases of the function, you are always multiplying both matrices. You will not be able to "end early" because you are always multiplying everything in the matrix. Because the function is bounded above and below by n^3, the function is bigTheta(n^3).

Lauren
  • 1