why O(n^{2}) ?

The Gateway to Computer Science Excellence

+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

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(n
^{2}) - n/1000= O(n
^{2}) - n= O(n
^{3}) - n
^{2}= O(n^{2}) - n
^{2}+n = O(n^{2})

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,429 answers

195,206 comments

99,915 users