CODEWITHSUNDEEP
algorithmbig-o
Prometheus
Prometheus

Reputation: 5

What is the exact runtime in Big-O of those functions

I wanted to ask if someone could answer this questions and also check my solutions. I don't really get the Big-O of these functions.

e(n)= n! + 2^n

f(n)= log10(n) * n/2 + n

g(n) = n2 + n * log(n)

h(n) = 2^30n * 4^log2(n)

I thought that:

e(n) n! because n! is exponentially rising.

f(n) n(log)n but I don't really know why

g(n) n^2

h(n) n

I would appreciate any answer. Thanks.

Upvotes: 0

Views: 61

Answers (1)

Tim Beatham
Tim Beatham

Reputation: 51

Big O notation allows us to evaluate the growth of a function with respect to some quantity as it tends towards a infinity.

The Big O notation of a function is that of it's fastest growing constituent. Big O notation bounds the growth of a function.

For example if a function is said to be O(n). There exists some k such that f(n) <= k * n for all n.

We ignore all other constituents of the equation as we are looking at values that tend towards infinity. As n tends towards infinity the other constituents of the equation are drowned out.

We ignore any constants as we are describing the general relationship of the function as it tends towards some value. Constants make things harder to analyze.

  1. e(n) = n! + 2^n. A factorial is the fastest growing constituent in the equation so the Big O notation is O(n!).

  2. f(n) = log10(n) * n/2 + n. The fast growing constituent is log10(n) * n/2. we say that the Big O notation is O(nlogn). It does not matter what base of log we use as we can convert between log bases by using a constant factor.

  3. g(n) = n^2 + n * log(n). The Big O notation is n^2. This is because n^2 grows faster than n * log(n) with respect to n.

  4. h(n) = (2^30) * n * 4 ^ log2(n). The time complexity is O(nlogn). The constants in this equation are 2^30 and 4 so we ignore these values. When doing this you can clearly see that the time complexity is O(nlogn).

Upvotes: 2

Related Questions