Mixing
What does a faster algorithm mean in theoretical computer science?
Clash Royale CLAN TAG#URR8PPP
up vote
17
down vote
favorite
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?
Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?
algorithms
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
asked Aug 9 at 13:32
lovw
20316
add a comment |Â
up vote
17
down vote
favorite
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?
Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?
algorithms
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
asked Aug 9 at 13:32
lovw
20316
4
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
1
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03
add a comment |Â
up vote
17
down vote
favorite
up vote
17
down vote
favorite
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?
Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?
algorithms
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
asked Aug 9 at 13:32
lovw
20316
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?
Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?
algorithms
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
asked Aug 9 at 13:32
lovw
20316
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
edited Aug 9 at 13:46
Yuval Filmus
181k12171329
181k12171329
asked Aug 9 at 13:32
lovw
20316
asked Aug 9 at 13:32
lovw
20316
asked Aug 9 at 13:32
lovw
20316
20316
4
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
1
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03
add a comment |Â
4
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
1
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03
4
4
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
1
1
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
26
down vote
accepted
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.
In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.
If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $Theta$ rather than just as a big $O$.
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
add a comment |Â
up vote
11
down vote
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.
Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n>10$.
So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n>100000$, which one would you pick? What would you do if your problem size varies greatly?
edited Aug 10 at 18:22
Glorfindel
135119
answered Aug 9 at 16:56
twalberg
2193
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
 |Â
show 1 more comment
up vote
5
down vote
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) in obigl(fleft(nright)bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.
Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $Theta(n^2)$ whereas we know others that run in $Theta(n log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.
And sometimes, even theoretical computer scientists use “faster†the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.†In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of asymptotic time complexity.
answered Aug 10 at 1:36
Davislor
63327
add a comment |Â
up vote
1
down vote
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.
To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.
The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.
If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.
Pick up the jar
Grab the lid
Unscrew the lid
Versus
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid
Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.
By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.
So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
answered Aug 10 at 21:41
Cort Ammon
2,484612
add a comment |Â
up vote
1
down vote
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) in O(f(n))$.
$$ exists 0 le c_f lt infty mid limsup_n to infty fracA(n)f(n) = c_f $$
Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $ limsup_ntoinfty g(n) = infty $ and let us create the function $ h(n) = fracf(n)g(n)$.
We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.
$$ exists 0 le c_h lt infty mid limsup_n to infty fracA(n)h(n) = c_h $$
Using the rules of limits, we can also write:
$$ c_h = limsup_n to infty fracA(n)h(n) = limsup_n to infty fracA(n)g(n)f(n) = c_f cdot limsup_n to infty g(n) $$
Since $c_h lt infty$, this can only be true if $c_f = 0$.
The contrapositive statement is: If $ c_f neq 0$, then $A(n) notin O(h(n))$.
In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) in Theta(f(n))$ and $g(n)$ is arbitrarily increasing.
Additionally, this should show why the statement that $A(n) in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
answered Aug 10 at 18:18
Jared Goguen
438
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
26
down vote
accepted
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.
In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.
If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $Theta$ rather than just as a big $O$.
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
add a comment |Â
up vote
26
down vote
accepted
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.
In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.
If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $Theta$ rather than just as a big $O$.
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
add a comment |Â
up vote
26
down vote
accepted
up vote
26
down vote
accepted
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.
In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.
If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $Theta$ rather than just as a big $O$.
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.
In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.
If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $Theta$ rather than just as a big $O$.
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
answered Aug 9 at 13:49
Yuval Filmus
181k12171329
181k12171329
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
add a comment |Â
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
21
21
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
It might be better to take $g(n)=1$ in your first paragraph. Using a decreasing function feels a little bit cheat-y.
– David Richerby
Aug 9 at 15:06
1
1
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
@DavidRicherby: Maybe a bit, but OP never said they had an algorithm running in $O(g(n))$ so monotonicity cannot be assumed.
– Kevin
Aug 10 at 2:58
7
7
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
@Kevin Sure but the context is computer science and, in computer science, big-O notation is usually used for nondecreasing functions. Probably the asker was thinking in those terms.
– David Richerby
Aug 10 at 11:48
add a comment |Â
up vote
11
down vote
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.
Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n>10$.
So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n>100000$, which one would you pick? What would you do if your problem size varies greatly?
edited Aug 10 at 18:22
Glorfindel
135119
answered Aug 9 at 16:56
twalberg
2193
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
 |Â
show 1 more comment
up vote
11
down vote
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.
Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n>10$.
So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n>100000$, which one would you pick? What would you do if your problem size varies greatly?
edited Aug 10 at 18:22
Glorfindel
135119
answered Aug 9 at 16:56
twalberg
2193
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
 |Â
show 1 more comment
up vote
11
down vote
up vote
11
down vote
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.
Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n>10$.
So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n>100000$, which one would you pick? What would you do if your problem size varies greatly?
edited Aug 10 at 18:22
Glorfindel
135119
answered Aug 9 at 16:56
twalberg
2193
Remember that $O(...)$ notation is meant for analyzing how the task grows for different sizes of input, and specifically leaves out multiplicative factors, lower-order term, and constants.
Suppose you have an $O(n^2)$ algorithm whose actual runtime is $1n^2+2n+1$ (assuming you can actually count the instructions and know the exact timings and so on, which is admittedly a huge assumption in modern systems). Then suppose you come up with a new algorithm that happens to be $O(n)$, but the actual runtime is $1000n + 5000$. Also suppose you know the software to use this algorithm will never see a problem size of $n>10$.
So, which would you chose - the $O(n)$ algorithm that's going to take 15000 units of time, or the $O(n^2)$ one that's only going to take 121 units? Now if your software evolves to handling problem sizes of $n>100000$, which one would you pick? What would you do if your problem size varies greatly?
edited Aug 10 at 18:22
Glorfindel
135119
answered Aug 9 at 16:56
twalberg
2193
edited Aug 10 at 18:22
Glorfindel
135119
edited Aug 10 at 18:22
Glorfindel
135119
edited Aug 10 at 18:22
Glorfindel
135119
135119
answered Aug 9 at 16:56
twalberg
2193
answered Aug 9 at 16:56
twalberg
2193
answered Aug 9 at 16:56
twalberg
2193
2193
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
 |Â
show 1 more comment
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
2
2
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
"never see a problem size of n>10" - then we'd not use the O notation at all, would we...
– AnoE
Aug 10 at 8:47
5
5
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
@AnoE Simple numbers for the sake of argument. The same logic applies whether you're analyzing for a problem size of 10 vs 1e5 or analyzing for 1e6 vs 1e9.
– twalberg
Aug 10 at 11:20
1
1
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
@AnoE Most computer programs do not try to handle an infinitely growing problem size. So there will be a trade-off. That's why big-O is for theoretical computer science, and the concepts can be applied to improve actual programs.
– mbomb007
Aug 10 at 14:04
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
Exactly, @mbomb007. The question title is "What does a faster algorithm mean in theoretical computer science?" and he has this in the body: "Does it make sense, in the context of theoretical computer science...".
– AnoE
Aug 10 at 14:25
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
@AnoE From experience, O notation is used when n<10 all the time! Not that it's a good idea... but it's totally something that's done!
– Cort Ammon
Aug 10 at 21:29
 |Â
show 1 more comment
up vote
5
down vote
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) in obigl(fleft(nright)bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.
Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $Theta(n^2)$ whereas we know others that run in $Theta(n log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.
And sometimes, even theoretical computer scientists use “faster†the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.†In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of asymptotic time complexity.
answered Aug 10 at 1:36
Davislor
63327
add a comment |Â
up vote
5
down vote
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) in obigl(fleft(nright)bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.
Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $Theta(n^2)$ whereas we know others that run in $Theta(n log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.
And sometimes, even theoretical computer scientists use “faster†the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.†In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of asymptotic time complexity.
answered Aug 10 at 1:36
Davislor
63327
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) in obigl(fleft(nright)bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.
Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $Theta(n^2)$ whereas we know others that run in $Theta(n log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.
And sometimes, even theoretical computer scientists use “faster†the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.†In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of asymptotic time complexity.
answered Aug 10 at 1:36
Davislor
63327
Generally, what that means is that, for any size of input that’s big enough, the old algorithm’s worst-case running time is slower than the new one’s. That’s equivalent to the formalism $g(n) in obigl(fleft(nright)bigr)$, where $g$ is the time complexity of the new algorithm and $f$ the time complexity of the old.
Sometimes, though, computer scientists care about average-case performance. The classic example is Quicksort: its worst-case runtime is $Theta(n^2)$ whereas we know others that run in $Theta(n log n)$ time, but it’s widely-used in practice because of its good average-case running time. It can additionally be tweaked to run very quickly in the cases that are most frequent in the wild, such as arrays that are mostly in the right order.
And sometimes, even theoretical computer scientists use “faster†the same way normal people do. For example, most implementations of String classes have Short String Optimization (also called Small String Optimization), even though it only speeds things up for short strings and is pure overhead for longer ones. As the input size gets larger and larger, the running time of a String operation with SSO is going to be higher by a small constant term, so by the definition I gave in the first paragraph, removing SSO from a String class makes it “faster.†In practice, though, most strings are small, so SSO makes most programs that use them faster, and most computer-science professors know better than to go around demanding that people only talk about orders of asymptotic time complexity.
answered Aug 10 at 1:36
Davislor
63327
edited Aug 11 at 0:01
answered Aug 10 at 1:36
Davislor
63327
answered Aug 10 at 1:36
Davislor
63327
answered Aug 10 at 1:36
Davislor
63327
63327
add a comment |Â
add a comment |Â
up vote
1
down vote
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.
To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.
The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.
If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.
Pick up the jar
Grab the lid
Unscrew the lid
Versus
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid
Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.
By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.
So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
answered Aug 10 at 21:41
Cort Ammon
2,484612
add a comment |Â
up vote
1
down vote
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.
To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.
The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.
If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.
Pick up the jar
Grab the lid
Unscrew the lid
Versus
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid
Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.
By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.
So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
answered Aug 10 at 21:41
Cort Ammon
2,484612
add a comment |Â
up vote
1
down vote
up vote
1
down vote
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.
To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.
The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.
If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.
Pick up the jar
Grab the lid
Unscrew the lid
Versus
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid
Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.
By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.
So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
answered Aug 10 at 21:41
Cort Ammon
2,484612
There is not one unified definition of what a "faster algorithm" is. There is not a governing body which decides whether an algorithm is faster than another.
To point out why this is, I'd like to offer up two different scenarios which demonstrate this murky concept.
The first example is an algorithm which searches a linked list of unordered data. If I can do the same operation with an array, I have no change on the big Oh measure of performance. Both searches are O(n). If I just look at the big Oh values, I might say that I made no improvement at all. However, it is known that array lookups are faster than walking a linked list in the majority of cases, so one may decide that that made an algorithm "faster," even though the big Oh did not change.
If I may use the traditional example of programming a robot to make a PBJ sandwich, I can show what I mean another way. Consider just the point where one is opening the jar of peanut butter.
Pick up the jar
Grab the lid
Unscrew the lid
Versus
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid
Even in the most academic theoretical setting I can think of, you'll find that people accept that the first algorithm is faster than the second, even though the big Oh notation results are the same.
By contrast, we can consider an algorithm to break RSA encryption. At the moment, it is perceived that this process is probably O(2^n), where n is the number of bits. Consider a new algorithm which runs n^100 faster This means my new process runs in O(2^n/n^100). However, in the world of cryptography, a polynomial speedup to an exponential algorithm is traditionally not thought of as a theoretical speed up at all. When doing security proofs, it's assumed that an attacker may discover one of these speed ups, and that it will have no effect.
So in one circumstance, we can change a O(n) to O(n), and call it faster. In a different circumstance, we can change a O(2^n) to O(2^n/n^100), and claim there was no meaningful speed up at all. This is why I say there is no one unified definition for a "faster algorithm." It is always contextually dependent.
answered Aug 10 at 21:41
Cort Ammon
2,484612
answered Aug 10 at 21:41
Cort Ammon
2,484612
answered Aug 10 at 21:41
Cort Ammon
2,484612
answered Aug 10 at 21:41
Cort Ammon
2,484612
2,484612
add a comment |Â
add a comment |Â
up vote
1
down vote
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) in O(f(n))$.
$$ exists 0 le c_f lt infty mid limsup_n to infty fracA(n)f(n) = c_f $$
Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $ limsup_ntoinfty g(n) = infty $ and let us create the function $ h(n) = fracf(n)g(n)$.
We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.
$$ exists 0 le c_h lt infty mid limsup_n to infty fracA(n)h(n) = c_h $$
Using the rules of limits, we can also write:
$$ c_h = limsup_n to infty fracA(n)h(n) = limsup_n to infty fracA(n)g(n)f(n) = c_f cdot limsup_n to infty g(n) $$
Since $c_h lt infty$, this can only be true if $c_f = 0$.
The contrapositive statement is: If $ c_f neq 0$, then $A(n) notin O(h(n))$.
In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) in Theta(f(n))$ and $g(n)$ is arbitrarily increasing.
Additionally, this should show why the statement that $A(n) in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
answered Aug 10 at 18:18
Jared Goguen
438
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
add a comment |Â
up vote
1
down vote
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) in O(f(n))$.
$$ exists 0 le c_f lt infty mid limsup_n to infty fracA(n)f(n) = c_f $$
Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $ limsup_ntoinfty g(n) = infty $ and let us create the function $ h(n) = fracf(n)g(n)$.
We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.
$$ exists 0 le c_h lt infty mid limsup_n to infty fracA(n)h(n) = c_h $$
Using the rules of limits, we can also write:
$$ c_h = limsup_n to infty fracA(n)h(n) = limsup_n to infty fracA(n)g(n)f(n) = c_f cdot limsup_n to infty g(n) $$
Since $c_h lt infty$, this can only be true if $c_f = 0$.
The contrapositive statement is: If $ c_f neq 0$, then $A(n) notin O(h(n))$.
In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) in Theta(f(n))$ and $g(n)$ is arbitrarily increasing.
Additionally, this should show why the statement that $A(n) in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
answered Aug 10 at 18:18
Jared Goguen
438
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) in O(f(n))$.
$$ exists 0 le c_f lt infty mid limsup_n to infty fracA(n)f(n) = c_f $$
Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $ limsup_ntoinfty g(n) = infty $ and let us create the function $ h(n) = fracf(n)g(n)$.
We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.
$$ exists 0 le c_h lt infty mid limsup_n to infty fracA(n)h(n) = c_h $$
Using the rules of limits, we can also write:
$$ c_h = limsup_n to infty fracA(n)h(n) = limsup_n to infty fracA(n)g(n)f(n) = c_f cdot limsup_n to infty g(n) $$
Since $c_h lt infty$, this can only be true if $c_f = 0$.
The contrapositive statement is: If $ c_f neq 0$, then $A(n) notin O(h(n))$.
In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) in Theta(f(n))$ and $g(n)$ is arbitrarily increasing.
Additionally, this should show why the statement that $A(n) in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
answered Aug 10 at 18:18
Jared Goguen
438
I can't comment yet, but I feel like the current answers, while correct and informative, do not address part of this question. First, let us write an expression equivalent to $A(n) in O(f(n))$.
$$ exists 0 le c_f lt infty mid limsup_n to infty fracA(n)f(n) = c_f $$
Now, let us assume we are talking about an arbitrarily increasing function $g(n)$ where $ limsup_ntoinfty g(n) = infty $ and let us create the function $ h(n) = fracf(n)g(n)$.
We are given that the run-time of the "improved" algorithm $A'(n)$ is in $O(h(n))$. Suppose that the run-time of the original algorithm $A(n)$ is also in $O(h(n))$. This can be written as follows.
$$ exists 0 le c_h lt infty mid limsup_n to infty fracA(n)h(n) = c_h $$
Using the rules of limits, we can also write:
$$ c_h = limsup_n to infty fracA(n)h(n) = limsup_n to infty fracA(n)g(n)f(n) = c_f cdot limsup_n to infty g(n) $$
Since $c_h lt infty$, this can only be true if $c_f = 0$.
The contrapositive statement is: If $ c_f neq 0$, then $A(n) notin O(h(n))$.
In words, $A'(n)$ is an "improvement" on $A(n)$ under the additional conditions that $A(n) in Theta(f(n))$ and $g(n)$ is arbitrarily increasing.
Additionally, this should show why the statement that $A(n) in O(f(n))$ is not strong enough to draw a conclusion about whether $A'(n)$ is an "improvement." In short, $A(n)$ could already be in $O(h(n))$.
answered Aug 10 at 18:18
Jared Goguen
438
edited Aug 11 at 4:29
answered Aug 10 at 18:18
Jared Goguen
438
answered Aug 10 at 18:18
Jared Goguen
438
answered Aug 10 at 18:18
Jared Goguen
438
438
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
add a comment |Â
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
1
1
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
Your limit should be limit superior.
– Yuval Filmus
Aug 10 at 22:24
1
1
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
@YuvalFilmus Updated
– Jared Goguen
Aug 11 at 4:30
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96108%2fwhat-does-a-faster-algorithm-mean-in-theoretical-computer-science%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
By "faster algorithm", we mean "asymptotically faster algorithm".
– Yuval Filmus
Aug 9 at 14:10
@YuvalFilmus what do you mean with "asymptotically"
– undefined
Aug 10 at 8:19
1
Running in time $o(f(n))$.
– Yuval Filmus
Aug 10 at 13:03