What is the complexity of function f(n),preferably the Big-O notation, and f(n) satisfies the condition n = f(n).log(f(n)) ,f(n) > 1 .Let assume that log in base 2.
I tried to isolate f(n) from the condition but could not get it done. After using excel to get the graph of function f(n). It seems that f(n) = O(n^2) but I cant figure out how to get it out?
Comments are getting long, so here's a sketch of a proof for you. This is probably homework, so please make sure you learn something instead of just copying it down.
In order to show that f is O(n), you have to show that there is an M and n1 where f(n) < M|n| for all n > n1.
We know that n = f(n) log(f(n)), so M |n| = M |f(n)| |log(f(n))|.
So what we are trying to find is an M and n1 for which
f(n) < M |n| = M |f(n)| |log(f(n))|
for n > n1.
n, f, and log f are all positive, so we can drop the |.| to get
f(n) < M f(n) log(f(n)) = M |n|
Our goal is to find an M and n1 for which
f(n) < M f(n) log(f(n)) = M |n|
is true for all n > n1. Pick M = 1, n1 = 10, then
f(n) < f(n) log(f(10)) <= f(n) log(f(n)) = |n| (where M is now set to 1)
for n > n1. f(n) log(f(10)) <= f(n) log(f(n)) is true because log(f(n)) is monotonic for n>n1 (homework exercise: show that this is true). f(n) < f(n) log(f(10)) is trivially true because log(f(10)) > 1.
This shows, then, that f(n) is O(n).