difference between T(n), Θ(n) and O(n) in algorithms

[warm arch]

From what I understand

• T(n) represents the exact time for an algorithm of a problem with size n,
• Θ(n) represents the asymptotic behavior of an algorithm as n approaches infinity (whatever that means.) There's something about I lower and upper bound that I remember as well.
• O(n) represents the time complexity of an algorithm.

To me, these three things (not even sure what to call them, or if they are all even the same thing) are extremely similar. I could not explain the difference between the three if my life depended on it. Anybody wiser and able to explain it a bit more?

[silver canopy]

Θ is both an upper and a lower bound

it means the algorithm in the worst case runs that slow and in the best case runs that fast

O is exclusively an upper bound

Because O is just an upper bound, if something is O(n), then it is also O(n^2), O(n!) etc...

both O and Θ are asymptotic as you say, which means they aren't concerned with the exact running time but rather how fast it grows

[warm arch]

I don't understand how something can be O(n^2) if it is originally O(n)..

[warm arch]

then what would the upper and lower bound of Θ(n) be? is it both n? How do you show the lower and upper bound using theta notation? Like what is the syntax, if that makes sense

[silver canopy]

If T(n)=O(f(n)) then that means f(n) grows at least as fast as T(n)

it's just an upper bound

since n^2 grows faster than n, if something is O(n) then it is also O(n^2)

[silver canopy]

Θ(n) means that the running time of the algorithm is in the worst case linear in the input and in the best case linear in the input

[warm arch]

im sorry this is still not making sense TT do you have some kind of anology that can help me visualize it or something?

I barely have a high school level of math knowledge btw..

[silver canopy]

then you should probably work on that to be honest

algorithmic analysis is pretty math-intensive

[warm arch]

yeah i know but that why i am here 😭

[silver canopy]

https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

try reading this

[warm arch]

I got thrown into this Algorithms course for some reason. they never warned me that it would have high levels of math. they didnt prepare me either. just went straight into it

do you perhaps have more resources on this for beginners?? i need to have to math knower to be able to keep up with class

[silver canopy]

i don't know what you know and what you don't know

but khan academy is good for everything high school level

the ideas used in introductory algorithms courses generally aren't that high level but require a certain degree of mathematical maturity

like having a good understanding of inequalities and functions

[warm arch]

thats fair yeah

[warm arch]

yeah its been almost 3 years since ive done anything like that

but ill check khan academy out thanks a lot!

[silver canopy]

[atomic owl]

.solved