CODEWITHSUNDEEP
mathbig-odiscrete-mathematics
Jigar Patel
Jigar Patel

Reputation: 157

Big Theta runtime analysis

I don't really understand the 2 questions below about T(n). I understand what theta means but I'm not sure about the answer for the questions. Can someone explain?

I thought that first one was false because T(2n/3) + 1 = Theta(log n) because the constant 1 added doesn't make a difference and log is closer to halving continuously but 2n/3 is not

I thought that second one was true because T(n/2) + n = Theta(n * log n) because the linear "n *" in Theta represents the "+n" in T(n/2) + n the "n/2" represents the log n in Theta...

enter image description here

Upvotes: 1

Views: 55

Answers (1)

Beta
Beta

Reputation: 99094

The first is Θ(log n).
Intuitively, when you multiply n by a constant factor, T(n) increases by a constant amount.
Example: T(n) = log(n)/log(3/2)

The second is Θ(n).
Intuitively, when you multiply n by a constant factor, T(n) increases by an amount proportional to n.
Example: T(n) = 2n

Upvotes: 2

Related Questions