Question

F(n)=n log n what is the most restrictive polynomial time asymptotic upperbound O(n^k) what is k?

Answer 1

For the function F(n) = nlogn

Let's first understand what is asymptotic upperbound - well it's upper limit of function by which it can't growth, doesn't matter how much input you provide to the function. Notice here it's simply upperbound not tightest upperbound. Tightest upperbound gives precise result.

if we assume g(n) = n^k

than g(n) is upperbound of F(n) only and only when it satisfies below condition --

F(n) <= g(n)

for any input of n in the function it is always less than g(n).

---------

if F(n) <= g(n)

F(n) <= n^k

log(F(n))* <= k ,,,, Base of Log is n here

Well basically K is constant whose value must be greater than certain number to just follow the F(n) <= g(n).

-----------------------------------------------------------------------------------------------------------------------------------------------------------

**Hope you are asking the same which I explain above, by the way question was little unclear what you exactly wanted to ask.

For any doubts and clarification please comment, if you want to ask different, also ask in comments.

Waiting for your positive feedback :)