Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

what is the difference between O(nk) and O(n+k) in time complexity?

In big O notation of time complexity in algorithmic analysis, when an algorithm depends on n and k, what is the difference between these two notations. Also pls help in the notation to use if there is a nested loop with outer loop running n times and inner loop running k times ?

like image 691
Gobi Krishnan Avatar asked Dec 04 '14 18:12

Gobi Krishnan


People also ask

Which is better O Logn or O n ))?

O(n) means that the algorithm's maximum running time is proportional to the input size. basically, O(something) is an upper bound on the algorithm's number of instructions (atomic ones). therefore, O(logn) is tighter than O(n) and is also better in terms of algorithms analysis.

Will O'n log n take more time or O n 2 take more time?

So, O(N*log(N)) is far better than O(N^2) . It is much closer to O(N) than to O(N^2) . But your O(N^2) algorithm is faster for N < 100 in real life.

What does O'n log n mean?

Logarithmic time complexity log(n): Represented in Big O notation as O(log n), when an algorithm has O(log n) running time, it means that as the input size grows, the number of operations grows very slowly. Example: binary search.

What is O n and O n2?

The letter “n” here represents the input size, and the function “g(n) = n²” inside the “O()” gives us an idea of how complex the algorithm is with respect to the input size. A typical algorithm that has the complexity of O(n²) would be the selection sort algorithm.


1 Answers

O(nk):

for( i=0; i<n; i++ ) {
   for( j=0; j<k; j++ )
   {}
}

O(n+k):

for( i=0; i<n; i++ )
{}

for( j=0; j<k; j++ )
{}
like image 119
Vadim Kalinsky Avatar answered Sep 30 '22 13:09

Vadim Kalinsky