The Gateway to Computer Science Excellence
+1 vote
1.1k views

The solution of the recurrence relation of $ T(n)=3T\left(floor \left(\frac{n}{4}\right)\right)+n$ is

  1. $O(n^{2})$
  2. $O(n/g n)$
  3. $O(n)$ 
  4. $O(l g n)$ 
in Algorithms by Boss (30.1k points)
recategorized by | 1.1k views

1 Answer

+2 votes

T(n) = 3T(floor (n/4))+ n  ~ 3T(n/4)+n

Apply Masters theorem

n ^ (log 4 3)  < n

Hence T(n) = Θ(n)

If T(n) = Θ(n) then T(n) = O(n)

If T(n) = Θ(n) then T(n) = O(n 2 )

answer can be A and C

Correct me if i am wrong

by Boss (32.5k points)
0

why O(n2) ?

0

f(n) = O(g(n)) means that if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n> n0.

Simply speaking, for a value n, f(n) will be always less than or equal to g(n).

In our case f(n) =n; then g(n) can be any thing that has value greater than equal to f(n)

Example:

  • n= O(n)
  • n= O(n2)
  • n/1000= O(n2)
  • n=  O(n 3)
  • n2 = O(n2)
  • n2+n = O(n2)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,206 comments
99,915 users