Algorithms sanjoy dasgupta solution manual

Since and have the same power of n.

Since n^1/2 is smaller than n^2/3

Since can always be overcome by above a particular , and so can it be less than below a particular .

Since

Since log 2n = log 2 + log n and log 3n = log 3 + log n.

which makes log 2 and log 3, just constants.

Since log n^2 = 2log n. and 2 is just a constant that can be dropped.

Since power greater than 0 can always overtake log at some point

On comparing n^2 is greater than n, and log’s are not that signifincant in comparison.

Since power greater than 0 can always overtake log at some point

Since (log n)^{(log n) -1} is greater than n for some value of n.

Since power greater than 0 can always overtake log at some point

Therefore, at some n g will overcome f, by comparison of powers.

Since n2^n will produce a greater value for n than 3^n at some point.

Since the two differ by a constant multiplicative factor, i.e.

2.

g(n) = 1