   Question about runtime
  This is about priority queue.My book claims that the runtime of changePriority(...) is O(log n). It changes priority of a node. So after the call we still have to do some stuff in order to maintain heap property( min priority at top ).My book uses Location Aware entry for its implementation. It claims thatremove and insert is O( log n) which I do not argue with. So for the question, inside the changePriority function my book uses the insertand the remove function. So at least the runtime of that function islog(n) + log(n), from the insert and remove.But log(n) + log(n) = 2log(n) = log(n^2). That is way different than log(n).Anyone want to enlighten me please why he claims its log(n)?The question might not be very clear, if thats the case then ask for more information please. Thanks.   
Quote:Original post by ConcentrateBut log(n) + log(n) = 2log(n) = log(n^2). That is way different than log(n).Anyone want to enlighten me please why he claims its log(n)?It's the shape of the function, not the constant factor. Running time of algorithm is better expressed as T(n) = k O(n) + C.For O-notation, only the O(n) matters. In practice, it's a composite of T(n) functions.Despite the big argument going on about P ?= NP, for sufficiently large constant factors a P solution is worse than NP.Practical example, in physics one of methods for solving n-body problem is multipole method. For 2D, IIRC, it behaves as O(n) function (which is better than nlogn with Barnes Hut or n^2 with naive), but actual number is O(n) = 40n. Compare that to nlogn, and O(n) solution is worse than nlogn for n<2^40.But in theory, O(n) solution is "better", assuming n goes to infinity. Similar problem happens with binary insertion sort vs. plain insertion sort, where effects of cache locality drive constant factors up, so that by time BIS outperforms plain version other sort algorithms are superior anyway.It's an asymptotic bound which describes general characteristic. For n^2 vs 2*log(n) the winner is clear. For O(n) notation, only the major factor is considered, so n^p, logb(n) or n.   ;  Ya I Guess. Since we go by the greatest degree as an approximation for runtime,I figured log(n^2) would be more appropriate.   ;Quote:Original post by ConcentrateYa I Guess. Since we go by the greatest degree as an approximation for runtime,I figured log(n^2) would be more appropriate.It's just a constant factor difference. Those aren't relevant for Big-O.   