it will be $O(n^{2})$

The Gateway to Computer Science Excellence

0 votes

0

same question already answered https://gateoverflow.in/11232/let-f-n-%CF%89-n-g-n-o-n-and-h-n-%D1%B3-n

+1 vote

0

@abhishekmehta4u

We can't say for sure that complexity is O(n^2)

As g(n) is omega (n), not O(n)

When we don't know the upper bound of g(n), we can't find out the upper bound of g(n).h(n)

However, we can say that it can be omega(n) for sure, at least.

We can't say for sure that complexity is O(n^2)

As g(n) is omega (n), not O(n)

When we don't know the upper bound of g(n), we can't find out the upper bound of g(n).h(n)

However, we can say that it can be omega(n) for sure, at least.

0

can u explain the steps i am not able to understand how does u get ???

if any links available then also it will be nice !!

@abhishekmehta4u

if any links available then also it will be nice !!

@abhishekmehta4u

+1

@vijju

what is the max and min value for this term [g(n)*h(n)] , min would be n as g(n) cant go below n and h(n) can become constant that case would give minimum value,

now think what can be its max value,you cant predict it

so for term [g(n)*h(n)] what you can surely say is its minimum value would be n, i.e omega(n)

now total exprsn is f(n)+[g(n)*h(n)], f(n) is theta(n) , it cant go beyond n or less than n ,so what you can say from total exprsn that value of this exprsn will always be greater or equal to n i.e omega(n)

what is the max and min value for this term [g(n)*h(n)] , min would be n as g(n) cant go below n and h(n) can become constant that case would give minimum value,

now think what can be its max value,you cant predict it

so for term [g(n)*h(n)] what you can surely say is its minimum value would be n, i.e omega(n)

now total exprsn is f(n)+[g(n)*h(n)], f(n) is theta(n) , it cant go beyond n or less than n ,so what you can say from total exprsn that value of this exprsn will always be greater or equal to n i.e omega(n)

- 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,645 questions

56,542 answers

195,692 comments

101,533 users