CODEWITHSUNDEEP
big-o
Darren
Darren

Reputation: 49

Is it valid to say the function f(n) = n is theta(n)?

I am taking a class and we're reviewing time complexity information.

I understand that big o is an upper bound, and omega is a lower bound, and if those are the same then the function is theta(that bound).

Let's say I have the function f(n) = n. Can we say that is is theta(n)?

I think it is because it is O(n) and Omega(n) for C=1 for k>=1, but I wanted to ask to be sure.

Upvotes: 0

Views: 463

Answers (1)

walnut
walnut

Reputation: 22162

Yes that is correct. It is a common definition to say that f \in \Theta(g) iff f \in \Omega(g) and f \in O(g).

Here f(n) = n and g(n) = n.

To prove both individual parts, liminf f(n)/g(n) = liminf 1 = 1 > 0 and limsup g(n)/f(n) = limsup 1 = 1 < \infty.

In particular f \in Theta(f) for all functions f.

Note however, that the notation usually uses a big \Theta, not a small one.

Upvotes: 1

Related Questions