- #1
Logik
- 31
- 0
Homework Statement
Prove that f(n) = n * log (n) is O(n(1+sqrt(n))).
Homework Equations
n/a
The Attempt at a Solution
I really don't know what to do else I wouldn't be here :? Some hints would be appreciated!
Well, you were given an f(n) and asked to proveLogik said:f(n) is O(g(n)) if and only if there exists an n_0 part of natural numbers and a constant C that is part of rational numbers for which f(n) <= that c*g(n) for all n >= n_o
I know the def just don't know how to get g(n)...
I think I had misunderstood you -- your last post sounded like you said you didn't know what g(n) was.Logik said:yes well I don't know how to go from f(n) to g(n)... the examples I have seen were just that you would multiply so part of f(n) until you could group everything together to get c* g(n) but this time I don't see how I can multiply anything to get anything that looks like g(n)...
Logik said:I don't know where to start to solve for c.. that is my problem...
This notation is known as Big O notation, which is a mathematical way to describe the limiting behavior of a function as its input grows. In this case, it means that the function f(n) grows no faster than n(1+sqrt(n)) as n increases.
To prove this, we need to show that there exists a positive constant c and a positive integer n0 such that f(n) <= c*n(1+sqrt(n)) for all n > n0. This can be done using mathematical induction or by using limits and derivatives.
The value of c represents the slope of the function, while n0 represents the point at which the function begins to follow the growth rate of n(1+sqrt(n)). A smaller value of c and larger value of n0 make the proof stronger, as it shows that the function follows the growth rate at a lower input and with a smaller slope.
Yes, this proof can be generalized for other functions by following the same logic and using the properties of Big O notation. However, the values of c and n0 may vary for different functions.
Big O notation allows us to analyze the efficiency and performance of algorithms and functions as the input grows. By proving the Big O notation of a function, we can determine how much time and space it will require to run, and compare it to other functions to choose the most efficient one for a given task.