 |  |  |  |  |  |  |  |
Time complexity of algorithm
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
 |
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation: 
Solved Threads: 139
If you feel like reading this post slowly and carefully, it will describe what this notation _really_ means.
All functions have some kind of behavior as n grows towards infinity. For example, if f(n) = 1/n, then as n grows towards infinity, f(n) gets closer and closer to zero. Whereas if f(n) = n*n, then as n grows towards infinity, f(n) grows too.
Functions can grow at different speeds. If two functions are equal, then they obviously grow at the same speed. But wait, there's more! Two functions are deemed to grow at the same speed if they're separated by a constant multiple! For example, if f(n) = n*n and g(n) = 3*n*n, then f and g are deemed to grow at the same pace, because g(n) = 3*f(n), so they are only a constant multiple apart. That is, g(n) / f(n) = 3, as n grows arbitrarily large.
But consider the scenario where f(n) = n * n, and g(n) = n. Then what is the behavior of f(n) and g(n) as n grows arbitrarily large? Well, f(n) / g(n) = (n * n) / (n). Which simplifies to f(n) / g(n) = n. Which means that as n grows large, f(n) = n * g(n). What does this mean? f and g are in this case not separated by a constant multiple. The multiple between f and g grows larger and larger as time progresses, without stopping. We say that "f grows faster than g" when this happens. Or "g grows slower than f". Just try some sample values of n: Try 10, 100, and 1000. First, f(10) / g(10) = 100 / 10 = 10. f(100) / g(100) = 10000 / 100 = 100. f(1000) / g(1000) = 1000000 / 1000 = 1000. We can easily see, hopefully, that the ratio between f and g is not constant.
Now consider the scenario where f(n) = 2 * n * n + 1, and g(n) = n * n. In this case, our functions have the ratio f(n) / g(n) = (2 * n * n + 1) / (n * n). What is the value of this ratio as n grows towards infinity? The answer is 2. Let's simplify the expression:
(2 * n * n + 1) / (n * n) =
(2 * n * n) / (n * n) + 1 / (n * n) =
2 + 1 / (n * n).
So f(n) / g(n) = 2 + 1 / (n * n).
So as n grows large, the term 1 / (n * n) gets arbitrarily (or rediculously) small. As n grows large, then, the value of (2 + 1 / n * n) gets closer and closer to 2.
We could plug in some values -- let's try 10, 100, and 1000 again.
f(10) / g(10) = (2 * 10 * 10 + 1) / (10 * 10) = 201 / 100 = 2.01
f(100) / g(100) = (2 * 100 * 100 + 1) / (100 * 100) = 20001 / 10000 = 2.0001
f(1000) / g(1000) = (2 * 1000 * 1000 + 1) / (1000 * 1000) = 2000001 / 1000000 = 2.0000001.
So the ratio between these two functions approaches a constant value as n grows large. Hence, f and g are said to grow at the same pace.
In comparing the growth rates of functions, we have these rules:
1. If f(n) / g(n) grows out of control, getting larger and larger as n gets larger, then f is said to grow faster than g.
2. If f(n) / g(n) settles towards some constant positive value, then f is said to grow at the same pace as g.
3. If f(n) / g(n) gets closer and closer to zero, then this means that its reciprocal, g(n) / f(n), is growing out of control, so g is said to grow faster than f. (Or f is said to grow slower than g.)
Now on to big O notation!
Big O notation actually refers to an entire _set_ of functions. The notation O(expression) represents the entire set of functions that grow slower than or at the same pace as expression. For example, O(n^2) represents the entire set of functions that grow slower than or at the same pace as n^2.
In other words, if g(n) = n, then since n grows slower than n^2, it follows that g lies in the set O(n^2). Likewise, if h(n) = 2 * n * n + 1, then since h grows at the same pace as n^2, it follows that h lies in the set O(n^2).
It's also true that h lies in the set O(n^3), because h grows slower than n^3. (Assuming the leading term is positive, quadratic functions always grow slower than cubic polynomials, which always grow slower than fourth-degree polynomials, which always grow slower than fifth-degree polynomials, and so on.)
Because O(expression) represents all the functions that grow _slower_ than or equal to expression, it is used to represent upper bounds.
The other notations refer to different sets of functions. For example, o(expression) represents all the functions that grow slower than expression (and not at the same speed.) f(n) = n^2 + n - 1 lies in the set O(n^2), but it doesn't lie in o(n^2). g(n) = n lies in both.
Theta(expression) represents all the functions that grow at the same rate as expression.
Omega(expression) represents all the functions that grow faster than or equal to expression.
In computer programs, we are of course interested in how much time it takes programs to run, and these forms of notation are useful for representing that, so that's why we use them. When you say an algorithm runs in O(expression) time, you're just saying that the algorithm's runtime is no worse than some multiple of expression. When you use Theta, you're saying that the algorithm's runtime is some multiple of expression. And Omega is used to say that the amount of time an algorithm takes to run grows at a rate that is larger than or equal to some expression's rate of growth.
(Disclaimer: some of the statements in this post are not strictly true, mathematically speaking. One that I noticed is that big O/Theta/etc notation uses a slightly different meaning of "grows slower" and "grows at the same speed" and "grows faster" than the ones I gave.)
All functions have some kind of behavior as n grows towards infinity. For example, if f(n) = 1/n, then as n grows towards infinity, f(n) gets closer and closer to zero. Whereas if f(n) = n*n, then as n grows towards infinity, f(n) grows too.
Functions can grow at different speeds. If two functions are equal, then they obviously grow at the same speed. But wait, there's more! Two functions are deemed to grow at the same speed if they're separated by a constant multiple! For example, if f(n) = n*n and g(n) = 3*n*n, then f and g are deemed to grow at the same pace, because g(n) = 3*f(n), so they are only a constant multiple apart. That is, g(n) / f(n) = 3, as n grows arbitrarily large.
But consider the scenario where f(n) = n * n, and g(n) = n. Then what is the behavior of f(n) and g(n) as n grows arbitrarily large? Well, f(n) / g(n) = (n * n) / (n). Which simplifies to f(n) / g(n) = n. Which means that as n grows large, f(n) = n * g(n). What does this mean? f and g are in this case not separated by a constant multiple. The multiple between f and g grows larger and larger as time progresses, without stopping. We say that "f grows faster than g" when this happens. Or "g grows slower than f". Just try some sample values of n: Try 10, 100, and 1000. First, f(10) / g(10) = 100 / 10 = 10. f(100) / g(100) = 10000 / 100 = 100. f(1000) / g(1000) = 1000000 / 1000 = 1000. We can easily see, hopefully, that the ratio between f and g is not constant.
Now consider the scenario where f(n) = 2 * n * n + 1, and g(n) = n * n. In this case, our functions have the ratio f(n) / g(n) = (2 * n * n + 1) / (n * n). What is the value of this ratio as n grows towards infinity? The answer is 2. Let's simplify the expression:
(2 * n * n + 1) / (n * n) =
(2 * n * n) / (n * n) + 1 / (n * n) =
2 + 1 / (n * n).
So f(n) / g(n) = 2 + 1 / (n * n).
So as n grows large, the term 1 / (n * n) gets arbitrarily (or rediculously) small. As n grows large, then, the value of (2 + 1 / n * n) gets closer and closer to 2.
We could plug in some values -- let's try 10, 100, and 1000 again.
f(10) / g(10) = (2 * 10 * 10 + 1) / (10 * 10) = 201 / 100 = 2.01
f(100) / g(100) = (2 * 100 * 100 + 1) / (100 * 100) = 20001 / 10000 = 2.0001
f(1000) / g(1000) = (2 * 1000 * 1000 + 1) / (1000 * 1000) = 2000001 / 1000000 = 2.0000001.
So the ratio between these two functions approaches a constant value as n grows large. Hence, f and g are said to grow at the same pace.
In comparing the growth rates of functions, we have these rules:
1. If f(n) / g(n) grows out of control, getting larger and larger as n gets larger, then f is said to grow faster than g.
2. If f(n) / g(n) settles towards some constant positive value, then f is said to grow at the same pace as g.
3. If f(n) / g(n) gets closer and closer to zero, then this means that its reciprocal, g(n) / f(n), is growing out of control, so g is said to grow faster than f. (Or f is said to grow slower than g.)
Now on to big O notation!
Big O notation actually refers to an entire _set_ of functions. The notation O(expression) represents the entire set of functions that grow slower than or at the same pace as expression. For example, O(n^2) represents the entire set of functions that grow slower than or at the same pace as n^2.
In other words, if g(n) = n, then since n grows slower than n^2, it follows that g lies in the set O(n^2). Likewise, if h(n) = 2 * n * n + 1, then since h grows at the same pace as n^2, it follows that h lies in the set O(n^2).
It's also true that h lies in the set O(n^3), because h grows slower than n^3. (Assuming the leading term is positive, quadratic functions always grow slower than cubic polynomials, which always grow slower than fourth-degree polynomials, which always grow slower than fifth-degree polynomials, and so on.)
Because O(expression) represents all the functions that grow _slower_ than or equal to expression, it is used to represent upper bounds.
The other notations refer to different sets of functions. For example, o(expression) represents all the functions that grow slower than expression (and not at the same speed.) f(n) = n^2 + n - 1 lies in the set O(n^2), but it doesn't lie in o(n^2). g(n) = n lies in both.
Theta(expression) represents all the functions that grow at the same rate as expression.
Omega(expression) represents all the functions that grow faster than or equal to expression.
In computer programs, we are of course interested in how much time it takes programs to run, and these forms of notation are useful for representing that, so that's why we use them. When you say an algorithm runs in O(expression) time, you're just saying that the algorithm's runtime is no worse than some multiple of expression. When you use Theta, you're saying that the algorithm's runtime is some multiple of expression. And Omega is used to say that the amount of time an algorithm takes to run grows at a rate that is larger than or equal to some expression's rate of growth.
(Disclaimer: some of the statements in this post are not strictly true, mathematically speaking. One that I noticed is that big O/Theta/etc notation uses a slightly different meaning of "grows slower" and "grows at the same speed" and "grows faster" than the ones I gave.)
Wow, I'm going to copy and keep that. Thank you very very much.
Quick question, since theta is an exact rate of growth, it can't have two values right, for the same algo/function?
Quick question, since theta is an exact rate of growth, it can't have two values right, for the same algo/function?
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation:
Solved Threads: 139
I don't understand your question; maybe rephrase it. But maybe this will answer it:
O(expression) is the set of functions that grow slower than or at the same rate as expression. Omega(expression) is the set of functions that grow faster than or at the same rate as expression.
Theta(expression) consist of all the functions that lie in both O(expression) and Omega(expression).
Now here's one of my attempts to target directly at what your question seems to be saying:
Suppose you've calculated that an algorithm takes f(n) operations, where f(n) = 3 * n^2 + 2 * n + 4. Since this polynomial grows at the same rate as n^2, then you could say that the function f lies in the set Theta(n^2). (It also lies in the sets O(n^2) and Omega(n^2) for the same reason.)
Here are some false statements:
f lies in Theta(n).
f lies in Theta(n^3).
These are false because the function f grows faster than n and grows slower than n^3.
However, here is a true statement:
f lies in Theta(n^2 + 1).
This is true because the function f grows at the same pace as n^2 + 1. Here are some other true statements:
f lies in Theta(2 * n^2).
f lies in Theta(3 * n^2 + 2 * n + 4).
f lies in Theta((n^2) / 45).
f lies in Theta(n^2 + 1 - 1).
f lies in Theta(n^2 + log(n)).
In each case, the function f grows at the same pace as the inside expression. (In one case, they're equal.)
So to answer your question: A function or an algorithm's runtime can be depicted by different theta expressions. However, these are equal theta expressions. Remember that Theta(n^2) refers to the set of all functions that grow at the same pace as n^2. Well, Theta(2 * n^2) refers to exactly the same set! (If a function grows at the same pace as n^2, then it also grows at the same pace as 2*n^2.)
Theta(2 * n^2) = Theta(3 * n^2 + 2 * n + 4) = Theta((n^2) / 45) = Theta(n^2 + 1 - 1) = Theta(n^2 + log(n)) = Theta(n^2).
If an algorithm's runtime has a theta bound, you can write the theta expression in different ways on _paper_, like above, but they mean the same thing. A function cannot have two _different_ theta bounds. (Different in that Theta(n^2) and Theta(n^3) represent completely different sets of functions.)
I would be writing the actual Greek character theta if I knew how to type it, by the way; writing out the word "Theta" is not normal.
O(expression) is the set of functions that grow slower than or at the same rate as expression. Omega(expression) is the set of functions that grow faster than or at the same rate as expression.
Theta(expression) consist of all the functions that lie in both O(expression) and Omega(expression).
Now here's one of my attempts to target directly at what your question seems to be saying:
Suppose you've calculated that an algorithm takes f(n) operations, where f(n) = 3 * n^2 + 2 * n + 4. Since this polynomial grows at the same rate as n^2, then you could say that the function f lies in the set Theta(n^2). (It also lies in the sets O(n^2) and Omega(n^2) for the same reason.)
Here are some false statements:
f lies in Theta(n).
f lies in Theta(n^3).
These are false because the function f grows faster than n and grows slower than n^3.
However, here is a true statement:
f lies in Theta(n^2 + 1).
This is true because the function f grows at the same pace as n^2 + 1. Here are some other true statements:
f lies in Theta(2 * n^2).
f lies in Theta(3 * n^2 + 2 * n + 4).
f lies in Theta((n^2) / 45).
f lies in Theta(n^2 + 1 - 1).
f lies in Theta(n^2 + log(n)).
In each case, the function f grows at the same pace as the inside expression. (In one case, they're equal.)
So to answer your question: A function or an algorithm's runtime can be depicted by different theta expressions. However, these are equal theta expressions. Remember that Theta(n^2) refers to the set of all functions that grow at the same pace as n^2. Well, Theta(2 * n^2) refers to exactly the same set! (If a function grows at the same pace as n^2, then it also grows at the same pace as 2*n^2.)
Theta(2 * n^2) = Theta(3 * n^2 + 2 * n + 4) = Theta((n^2) / 45) = Theta(n^2 + 1 - 1) = Theta(n^2 + log(n)) = Theta(n^2).
If an algorithm's runtime has a theta bound, you can write the theta expression in different ways on _paper_, like above, but they mean the same thing. A function cannot have two _different_ theta bounds. (Different in that Theta(n^2) and Theta(n^3) represent completely different sets of functions.)
I would be writing the actual Greek character theta if I knew how to type it, by the way; writing out the word "Theta" is not normal.
Sorry, that was a stupid question. I understood my own question on a second read of your earlier post, thanks again.
Verifying if anyone could give me a hand solving this excersices:
Instructions:
Find the Big Oh for the times which is excecuted x : = x + 1. You should justify your answer:
I : = N
WHILE I >= 1 DO
BEGIN
FOR J : = 1 TO N DO
X : = X + 1
I = [I/2]
END
Instructions:
Find the Big Oh for the times which is excecuted x : = x + 1. You should justify your answer:
I : = N
WHILE I >= 1 DO
BEGIN
FOR J : = 1 TO N DO
X : = X + 1
I = [I/2]
END
hey every body
great conversation..!
but can you tell me how to look to the algorithm to calculate the time complexity
great conversation..!
but can you tell me how to look to the algorithm to calculate the time complexity
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation:
Solved Threads: 139
Count the total number of fundamental operations the algorithm performs, relative to some value N. For example, this function..
The function sets the value of ret to 1. This is one operation.
Then this function tests the condition of the while loop exactly 1 + n times. It runs the body of the while loop exactly n times. The body of the while loop performs exactly 2 fundamental operations: 'multiply ret by n', and 'decrement n'. The condition has one fundamental operation, comparison. Calling the function counts as a fundamental operation, too.
So we have the total number of fundamental operations being
1 + 1 + (1 + n) + 2 * n. (The sum is composed of the operations for calling the function, setting ret = 1, performing a total of 1 + n tests in the condition of the while loop, and a total of 2 * n operations in the body of the while loop.)
This simplifies to 3 + 3 * n fundamental operations, which is O(n).
(What do I mean by 'fundamental operation'? Any operation that takes an amount of time that is bounded by a constant.)
int factorial(int n) {
int ret = 1;
while (n != 0) {
ret *= n;
-- n;
}
return ret;
}The function sets the value of ret to 1. This is one operation.
Then this function tests the condition of the while loop exactly 1 + n times. It runs the body of the while loop exactly n times. The body of the while loop performs exactly 2 fundamental operations: 'multiply ret by n', and 'decrement n'. The condition has one fundamental operation, comparison. Calling the function counts as a fundamental operation, too.
So we have the total number of fundamental operations being
1 + 1 + (1 + n) + 2 * n. (The sum is composed of the operations for calling the function, setting ret = 1, performing a total of 1 + n tests in the condition of the while loop, and a total of 2 * n operations in the body of the while loop.)
This simplifies to 3 + 3 * n fundamental operations, which is O(n).
(What do I mean by 'fundamental operation'? Any operation that takes an amount of time that is bounded by a constant.)
All my posts may be redistributed under the GNU Free Documentation License.
•
•
•
•
Originally Posted by Rashakil Fol
Count the total number of fundamental operations the algorithm performs, relative to some value N. For example, this function..
int factorial(int n) { int ret = 1; while (n != 0) { ret *= n; -- n; } return ret; }
The function sets the value of ret to 1. This is one operation.
Then this function tests the condition of the while loop exactly 1 + n times. It runs the body of the while loop exactly n times. The body of the while loop performs exactly 2 fundamental operations: 'multiply ret by n', and 'decrement n'. The condition has one fundamental operation, comparison. Calling the function counts as a fundamental operation, too.
So we have the total number of fundamental operations being
1 + 1 + (1 + n) + 2 * n. (The sum is composed of the operations for calling the function, setting ret = 1, performing a total of 1 + n tests in the condition of the while loop, and a total of 2 * n operations in the body of the while loop.)
This simplifies to 3 + 3 * n fundamental operations, which is O(n).
(What do I mean by 'fundamental operation'? Any operation that takes an amount of time that is bounded by a constant.)
Not everyone is a math nerd like you.
I'm here to prove you wrong.
•
•
Join Date: Jun 2005
Posts: 2,039
Reputation:
Solved Threads: 139
Sure, that's how everybody solves the problem, but that sort of explanation lacks clarity and makes out the process to be some sort of magic voodoo.
Besides, you're really doing the same thing I explained, only you're calculating the algorithm's complexity via the route O(1) * O(n) + O(1) = O(n), substituting big O notation a bit earlier.
Besides, you're really doing the same thing I explained, only you're calculating the algorithm's complexity via the route O(1) * O(n) + O(1) = O(n), substituting big O notation a bit earlier.
All my posts may be redistributed under the GNU Free Documentation License.
>Besides, you're really doing the same thing I explained
Kinda sorta. You're counting individual operations and I'm just looking for loops and deriving the complexity from a guestimate of how many times a loop iterates.
>but that sort of explanation lacks clarity
I think it adds clarity by removing the complicated intermediate junk that overwhelms so many people. Accuracy isn't always synonymous with clarity. Take the C++ standard. It's written with accuracy in mind, and the language used emphasizes that. But I don't know anyone who would say that it's immediately clear what's being said.
>makes out the process to be some sort of magic voodoo.
Not really. It's all about the iteration counts. Once you have those, a simple ruleset will give you what you want. For example, n nested in n is O(n^2). n and n not nested is O(n). log n nested in n is O(n*log n). Once someone knows the notation and what each one means, it's very intuitive. The "right" way (in my experience) confuses the hell out of people.
That's not to say that the right way is unnecessary. I just think you're flip flopping the order when the simple way should be learned first, then once the concepts are understood, the right way can be introduced for a more thorough understanding.
Kinda sorta. You're counting individual operations and I'm just looking for loops and deriving the complexity from a guestimate of how many times a loop iterates.
>but that sort of explanation lacks clarity
I think it adds clarity by removing the complicated intermediate junk that overwhelms so many people. Accuracy isn't always synonymous with clarity. Take the C++ standard. It's written with accuracy in mind, and the language used emphasizes that. But I don't know anyone who would say that it's immediately clear what's being said.
>makes out the process to be some sort of magic voodoo.
Not really. It's all about the iteration counts. Once you have those, a simple ruleset will give you what you want. For example, n nested in n is O(n^2). n and n not nested is O(n). log n nested in n is O(n*log n). Once someone knows the notation and what each one means, it's very intuitive. The "right" way (in my experience) confuses the hell out of people.
That's not to say that the right way is unnecessary. I just think you're flip flopping the order when the simple way should be learned first, then once the concepts are understood, the right way can be introduced for a more thorough understanding.
I'm here to prove you wrong.
|
Similar Threads
- calculate time complexity of the algorithm (Computer Science)
- time complexity of algorithm (Computer Science)
- Calculating time complexity (Computer Science)
- Help On Time Complexity Algorithm (Computer Science)
Other Threads in the Computer Science Forum
- Previous Thread: Breakthrough heralds new era of cognitive computing
- Next Thread: Is prostitution more enjoyable than programming?
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest Computer Science Posts
- Today's Posts
- Unanswered Threads
