O(sin n), Ω(sin n), Θ(sin n) complexity

[ulita]

Hello , Do you know examples of functions belonging crowds O(sin (n)), Ω (sin (n)), Θ (sin (n)) ?

 

[mathman]

You could define what those terms mean.

 

[CRGreathouse]

http://mymathforum.com/viewtopic.php?f=44&t=15362

 

[disregardthat]

I'm quoting (presumably) you from your link:

it's easy to see that (among others) all positive functions are in Ω(sin n).

Are you sure about this? What about $$f(n) = 2^{-n}$$ ?

Positive functions with a global minimum would be one class of functions which belongs to Ω(sin n).

 

[CellCoree]

The complexity of a function refers to the amount of time and resources required to run it. In this case, the functions O(sin n), Ω(sin n), and Θ(sin n) all have a complexity that is related to the sine function.

The O(sin n) complexity represents the upper bound of the function, meaning that the function will not take longer than O(sin n) time to run. This could include functions such as sorting algorithms, where the time it takes to sort a list of numbers is directly related to the size of the list. As the list size increases, the time it takes to sort also increases, but it will not exceed O(sin n) time.

On the other hand, the Ω(sin n) complexity represents the lower bound of the function, meaning that the function will not take less than Ω(sin n) time to run. An example of this could be a search algorithm, where the time it takes to find a specific element in a list is directly related to the size of the list. As the list size decreases, the time it takes to find the element also decreases, but it will not take less than Ω(sin n) time.

Finally, the Θ(sin n) complexity represents the average case of the function, meaning that the function will take approximately Θ(sin n) time to run. This could include functions such as calculating the average of a list of numbers, where the time it takes is directly related to the size of the list, but is not affected by the specific values in the list.

In terms of specific examples, some functions that belong to each of these complexity classes could include:

- O(sin n): Merge sort, quicksort, and other sorting algorithms that have a worst-case time complexity of O(n log n).
- Ω(sin n): Linear search, binary search, and other search algorithms that have a best-case time complexity of Ω(1).
- Θ(sin n): Selection sort, bubble sort, and other sorting algorithms that have an average-case time complexity of Θ(n^2).

It is important to note that the complexity of a function can vary depending on the specific implementation and input data, so these examples are not definitive and other functions could also belong to these complexity classes.