Menu
I am trying to solve this recurrence
T(n) = 3 T(n/2) + n lg n ..
I have come to the solution that it belongs to masters theorem case 2 since n lg n is O(n^2)
but after referring to the solution manual i noticed this solution that they have
The soluttion says that n lg n = O ( n ^(lg 3 - e)) for e between 0 and 0.58
so this means n lg n is O(n) .. is this right? Am i missing something here?
Isn't nlgn O(n^2) ?
398
O(log N) basically means time goes up linearly while the n goes up exponentially. So if it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100 elements, 3 seconds to compute 1000 elements, and so on. It is O(log n) when we do divide and conquer type of algorithms e.g binary search.
Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.
logarithm, the exponent or power to which a base must be raised to yield a given number. Expressed mathematically, x is the logarithm of n to the base b if bx = n, in which case one writes x = logb n. For example, 23 = 8; therefore, 3 is the logarithm of 8 to base 2, or 3 = log2 8.
Yes for Binary search the time complexity in Log(n) not nlog(n). So it will be less than O(n). But N*Log(N) is greater than O(N).
This will explain things better 
145
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
