O (n ^ 2) is greater than O ((n ^ 2) logn)
O (n ^ 2) more than O (n ^ 2 log n)?
If yes? as? May we have a simple example for this. Also,
what is the complexity of the code below.
int unknown(int n){
int i,j,k=0;
for(i=n/2;i<=n;i++){
for(j=2;j<=n;j=j * 2){
k =k + n/2;
}
}
return k;
}
and what is the complexity of the return value k?
source to share
O(n^2)
is a subset O((n^2) * log(n))
, and therefore the first is "better", it is easy to see that since it log(n)
is an increasing function, multiplying something with it you get "higher", then the original ( f(n) <= f(n) * log(n)
for each increasing function is not negative f
and n>2
)
The code you provided is O(nlog(n))
, since the inner loop repeats log(n)
once for each iteration of the outer loop, and the outer loop repeats n / 2 times - which gives you n/2 * log(n)
which is inO(nlog(n))
source to share
I assume you mean it O((n^2) * log n)
, but the answer is the same and what you need to prove is basically the same if it is n^(2 * log n)
. I will also only consider non-negative functions to save some of the absolute mess.
The answer lies in what O(n^2)
is a strict subset O((n^2) * log n)
. It is smaller.
First, we prove its subset: let f
- O(n^2)
. Then there are M
, and k
such that for all n >= M
, f(n) <= k(n^2)
.
Let L = max(M, e)
(where e is the logarithmic base). Then for all n >= L
, log(n) >= log(e) == 1
(since n >= 1
) and f(n) <= k(n^2)
(since n >= M
).
Consequently, for all n >= L
, f(n) <= k(n^2) * log(n)
. So f
is in O((n^2) * log n)
.
Second, prove it by a strict subset: let g
is a function g(n) = (n^2) * log n
, therefore g
is in O((n^2) * log n)
.
k
Let's take for anyone L = e^k
. Then for any n > L
, log(n) > k
and therefore g(n) > n^2 * k
.
Consequently, g
there is not O(n^2)
, as there is no such M
, and k
that for all n >= M
, g(n) <= k * n^2
.
source to share