Question

T(n),Θ(n)

who can help me understand T(n) and Θ(n) differences

and also what does numeric have to do with asymptotic. why some people use them so as the one is oposite to the other ?

Answer 1

T(n) and O(n) maybe two functions ? ... do you can rewrite them here ?

Answer 2

In computer science, assuming that is what this is, there is three main types of notation used to express [time] complexity (optionally proportional to input size).

1. Big O notation = \(O(n)\)
2. Big Omega notation = \(\Omega(n)\)
3. Big Theta notation = T(n) = \(\Theta(n)\)

Complexity of an algorithm is often tested against an arbitrarily large input. (So asymptotically versus numerically.)

For computer science big O notation focuses on the shape of the curve as something (i.e. algorithm) scales (to an arbitrarily large input, an example would be the divide and conquer algorithm). I think you can understand from here that big O is not a measure of actual performance, rather a reference on how an algorithm should preform, rather than the actual performance (theoretical versus test case). Due to big O being used like this it abstracting away details unimportant, constant factors are left to make no difference. Basically functions are turned into equivalence classes based on their upper bounds.

When we being to merge test-case and the theoretical, and want more precise notions of running time. Due to everything being measured asymptotically we have big Theta notation that describes equivalence, and big Omega notations that describe lower-bounds.

TL;DR
\(O(n)\) is the asymptotic upper bound.
\(\Omega(n)\) is the asymptotic lower bound.
\(\Theta(n)\) is the asymptotic tight bound. (Upper and lower.)

Answer 3

@Christos so what is your opinion about these ?

Answer 4

@Opcode nice work !!!

Answer 5

@jhonyy9 thank you, I just hope one can understand it. Generally big O concepts are taught along side a programming language, which is much easier to communicate ideas. (At least for me it is.)

A more visual explanation rather than text: http://teachingtree.co/watch/divide-and-conquer
While it is not about teaching about the notation, he used big Theta notation, and you can understand it implicitly. @Christos

Answer 6

I just read from a book that T(n) represents the time complexity that an algorithm has, or in other words the number of instructions that it executes. And then there is Θ(n), which according to the book it is the asymptotic tight bound as you have said.

Are you sure T(n) = Θ(n) ? Is Θ(n) representing the time complexity ? Is T(n) representing the asymptotic tight bound of an algorithm ?


also can someone explain to me what is asymptotic ?

Answer 7

@Opcode , @jhonyy9

Answer 8

Is this your first time looking at time complexity analysis?

Answer 9

Big o examples: http://bigocheatsheet.com/

Answer 10

for example https://www.dropbox.com/s/2uqnz0c0wkwshp8/Screenshot%202015-12-30%2021.07.37.png?dl=0

Answer 11

@OPcode can you clarifay plz