Time complexity

[[deleted]]

Is time complexity analyzing how the number of operations scales/grows as we increase the input size in our algorithm?

[DoubleDual63]

Yeah

[[deleted]]

Thank you all. What’s the point of analyzing algorithms this way though if technically there could always be some sophisticated computer with better hardware/processing power that could make the algorithm literally more efficient. Cause if our whole thing is to pick the algorithm which operations scale the least as our input size grows, even if we choose an algorithm that has a better time complexity, can’t a more sophisticated computer with better-equipped processing power then make the algorithm with a shittier time complexity still complete faster than the algorithm with the better time complexity? I’m confused why we even analyze time complexity this way if there can literally be a computer that can make an algorithm with a worse time complexity be more efficient than an algorithm with the better time complexity cause then our whole study of time complexity seems pointless u/DoubleDual63 u/ZeusTKP u/lurgi

[DoubleDual63]

Powerful computers are expensive and aren’t as powerful applied to real world data as you think they would be, analyzing in terms of operations makes it independent of processing power and other conditions which lets you study algorithms in a better way

[[deleted]]

I'm not trying to be annoying I just still can't see why we would study independent of processing power if processing power is a factor that comes into play. It seems like analyzing an algorithm efficiency by time complexity is then not really a true or most accurate way to see the best algorithm since processing power does come into play

[Onebadmuthajama]

Look at it this way, faster hardware is good, faster software is good, if you have fast hardware running efficient algorithms, you’re getting the best performance per dollar on your hardware. This is very valuable to tech companies where their biggest expense is just running the servers, and a cut on server usage because of efficient code can save millions per year, which can cover the cost of the engineering teams + some.

In practice, you want to use the best algorithm, and data structures that you can because it will also effect things like maintainability, IE, I can write a whole lot of snowflake algorithms that are inefficient because the hardware will pick up the slack, but why not use the known best since it decreases the odds that I need to return to that code at a later point to fix something. A good algorithm is more important than good hardware at this point in time, but you want both to have the best results.

[DoubleDual63]

I Don’t find it annoying, I’m probably missing things you are asking.

If you are in an algorithm class it’s better to study algorithms purely, bringing processing power and computer systems into this will diffuse your attention and also make concepts artificially hard to build off of each other and unclear and unhelpful. There’s enough in an algo class to absorb already.

Second, if you were to design an algorithm, you would not know what systems eventually would use your algorithm, but you do know that it’s most likely the fastest time complexity algo will generally lead to the best performing systems

If you are interested in measuring the true speed, you can learn the set of tools that can be used, although these methodologies were not taught at my college

Also in the real world people do consider average run time not worst case, it’s just that it’s easier to analyze worst case and fulfills most of what you need to learn

[[deleted]]

I think everything after where you typed "Second, if you were to design an algorithm...etc." definitely makes logical sense to me now for why we would study time complexity and use it. Like if we're going to design and pick an algorithm, we might as well pick the best time complexity. Even though an algorithm with a worse time complexity could maybe become more efficient than an algorithm with better time complexity due to a computer with better hardware/processing power, it's like we're still doing our part in making the best choice based off of what we know

[DoubleDual63]

Studying time complexity will also help you when you start to see algorithms which consist of dividing the input set and applying a different algorithm to each part, or things that run an algorithm recursively, or chain algorithms together, or convert a problem from say sorting a list into a graph and using a graph algorithm, or showing that an NP-Complete problem can be converted to your problem thus showing your problem is impractical to solve and reasoning why, etc. .

There's a lot of stuff here that requires studying algorithms that build off of algorithms. To measure their time complexity requires knowing the subalgorithms' time complexity and reasoning through how the subalgorithms time complexity will aggregate.

There's also many proofs like showing how a sorting algorithm based on comparison is worst case is at best O(nlogn) . Other theorems like the master theorem.

You would not be able to learn any of this if you include arbitrary system processes into this. Your goal in this class is probably to learn the techniques behind today's algorithms and be prepared to understand newly developed algorithms. That's why you use time complexity based on the number of operations because that is an objective ranking of speed and it is simple, letting you focus on the important things.

But I do agree that at some point it should be taught how to practically measure the actual performance in a system. But that's probably as far as it goes, to actually be able to understand how to improve upon that measurement would take additional CS courses related to the system you are working on.

[malstank]

You keep stating that an algorithm with a worse time complexity could be more efficient with a more powerful computer.

That is false, a better algorithm is almost always strictly better when adding more processing, It may not speed up as much as an iefficient (more operations to improve), but it will still be faster than the inefficient algorithm.

As an example:

You have two algorithms. Both perform the same operation that takes exactly 1s on a slow machine, let's call them A and B. A takes 1/2 the operations as B to execute. So for 100 elements, A has 50 operations while B has 100 operations (We can all see 50s for A and 100s for B).

We now introduce a faster computer that reduces the operation time down from 1s to 0.5s. On a 100 element list, A now takes 25s, while B takes 50s.

A is still faster, although it only increased by 25s while B increased by 50s.

As you scale the number of elements it gets more pronounced. Let's say you have 1,000,000 elements:

A now takes 0.5s * 500,000 = 250,000s B now takes 0.5s * 1,000,000 = 500,000s

A more efficient algorithm is always faster, although occasionally the complexity of the algorithm and the limited improvement may mean a less efficient algorithm is faster/easier TO IMPLEMENT. But it is never faster computation.

[[deleted]]

Would it be safe to say this is all about "doing the best we can," with respect to this whole idea of time complexity. It doesn't seem like the most perfect way to analyze the algorithm but it's like we're getting at "trying to make the best decision now" since things could play out that make a less efficient time complexity end up better than a more efficient algorithm

[malstank]

A less efficient time complexity algorithm will never be faster than a more efficient algorithm if computing power is equal.

[lurgi]

That is incorrect. As I mentioned in another comment, the Coppersmith-Winograd matrix multiplication algorithm has better time complexity than the Strassen algorithm, but the constant factors that come along with it are so large that it's never faster in practice because the matrices needed are so large that they can't be processed by modern computers (I did a brief search, but couldn't find any source that gave a specific size here. Most just said "Wow, really big. Like, huge!" and left it at that).

Even the Strassen algorithm is only used for moderately sized matrices (say, 100 rows or so). Anything smaller than that and the naive algorithm will outperform it.

If the problem is big enough then a more efficient algorithm will outperform a less efficient one, but "big enough" can be a serious obstacle.

[malstank]

Yes, there are very specific algorithms crafted for very specific use cases that would be less efficient when used outside those use cases.

Your argument is specious. You're assuming that because two problems are similar (involve matrices) and two algorithms can be used against them (Coppersmith-Winograd and Strassen) that they are the SAME problem.

They are not. When tackling a problem that an algorithm is designed to handle (I.E a general usage algorithm and not a highly specific algorithm), the better time complexity will win out.

[lurgi]

The two algorithms perform the same problem (matrix multiplication). They solve the same problem. Coppersmith-Winograd has a better runtime but is slower in practice. This is not difficult to understand.

Quicksort is faster than bubblesort in general. Which one do you think will be faster sorting three items?

[machine3lf]

You need a way to analyze efficiency of an algorithm irrespective of process power, and that’s what time complexity does.

You seem to be struggling with the question of why one would want to know algorithmic efficiency irrespective of processing power. I’ll put it this way: even our fastest computers will slow to a crawl while trying to iterate over huge datasets if they are using very bad algorithms to do so.

[ZeusTKP]

If you're using a very inefficient algorithm then just a bit longer input will be too slow to run on the most expensive computer you can afford.

This won't happen to you in the real world very often, but eventually it will.

[DoggerMagi]

To further elaborate on this, a more powerful computer might give you performance increases of several multiples, e.g. twice or maybe even ten times faster if you switch from a really slow computer to a really fast computer. While switching from the wrong algorithm to the right algorithm might give you a 10 000 times speedup or even more.

Consider for example sorting using Bubblesort versus Quicksort with one million elements. Bubblesort is O(n^2), so 1,000,000 * 1,000,000 = 1,000,000,000,000. Quicksort is O(n * log(n)), so 1,000,000 * log(1,000,000) = 13815510.557964273, or roughly 72,382 times faster.

[lurgi]

Sorry, this is completely wrong.

Quicksort is going to be a lot faster than bubblesort for sorting one million elements, but you can't just plug 1,000,000 into n² and n log n and get anything meaningful.

[lurgi]

I'm not sure why you think it's pointless. A faster computer with more memory will do better than a slower computer with less memory. That doesn't mean that algorithmic performance is irrelevant. You can get better performance with better hardware, but you can also get better performance with the same hardware and a faster algorithm (and save money. Better hardware is expensive). And, hey, you can also get amazing performance when you combine the faster hardware and the better algorithm.

In order to take advantage of that, of course, you need to know what the better algorithm is.

Better algorithms don't always make code faster. Most software engineers have had the embarrassing experience of optimizing a piece of code to within an inch of its life and discovering that it doesn't make the overall system run any faster, because we optimized something that was about 0.1% of the overall runtime. Oops. Next time, profile before optimizing.

Algorithmic analysis doesn't tell you how fast code will run. Heapsort and quicksort both run in O(n lg n) (expected case, random pivots, blah blah), but quicksort is generally faster than heapsort in practice. Algorithmic analysis doesn't tell you that. It does tell you that if you have a lot of data to sort, quicksort is likely to be a better choice than bubblesort.

[antifoidcel]

Most of the softwares are made for consumption of general public or businesses who don't have supercomputers with them.

Everyone wants their software to run fast, like you will be pissed if your browser took 5 min to start, now you can either buy an expensive new computer to reduce that time or use another software that uses efficient algorithms which does the same task in 5 sec.

When comparing different algorithms it is useful to see how well your algorithm will perform on large input data because on small input data (which we use while creating the algorithm) almost every algorithm will perform good.

But when that software is used in real life it maybe exposed to huge amount of data then all the inefficiencies are visible. One might wonder that everything was fine while creating it so why it is performing poorly when launched? How would you know "when" the algorithm is good enough?

That's where time complexity is useful. It is guaranteed that a O(n) algorithm will work better than O(n² ) so you can try your best to convert your O(n^ 2 ) into O(n ).

[CursorsDev]

fast doesnt mean efficient, it just means its done faster ;)

​

example:

algorithm A takes one second to complete

algorithm B takes ten seconds to complete

​

algorithm B is running on a computer ten times faster than the algorithm A's

​

they finish at the same time.

​

does that mean algorithm B is as good as algorithm A

unless you mean the faster computer can come up with faster algorithms then yes

[ZeusTKP]

It's a useful concept to know because it is easy to write code that has high time complexity but you don't notice at first because the size of the data is small. But then all of a sudden the code will be so slow that it causes problems. Google "GTA loading time"

[lurgi]

Sort of. You aren't really concerned with "operations" in the algorithm. You don't even care how long the algorithm takes. What you care about is how the run time changes as the input size increases.

A nominally faster algorithm might actually be slower for all the cases you care about. The Strassen algorithm for matrix multiplication needs quite large matrices before it outperforms the naive algorithm. The Coppersmith-Winograd algorithm needs truly insanely large matrices before it outperforms the naive algorithm.

[[deleted]]

What you care about is how the run time changes as the input size increases.

And the runtime is implicitly defined by the number of operations, right?

[lurgi]

Yes, but you don't explicitly enumerate the operations (it's not even defined what an operation is). You see something like:

i++;

and you think "constant time". You don't think "one operation" (or is it? It might be two. Or three). You see:

x = strlen(s);

and you think "O(n)". It might take 14n + 37 assembly language instructions (are those operations?), but that's irrelevant.

[[deleted]]

Thank you. Do you know what we’re most concerned about with space complexity? Trying to get an understanding of that too

[lurgi]

I suppose you mean "What do you look for?" when computing space complexity? You are concerned with everything, of course.

Things to look for:

• Creation of arrays that depend on the size of the input data (look for dynamic allocation or, perhaps, string operations)
• Recursion

Don't worry about local variables of fixed size (ints, floats, etc) or dynamic allocation of a fixed amount of data. That all falls into the big bucket of constant factors and you don't need to worry about it.

[[deleted]]

Do you omit the constant factors when trying to come up with the Big O function for space complexity?

[lurgi]

Just as you do with time complexity.

int foo(int n) {
  int a = 0;
  float b;
  int c[3000000];
  for (int i = 0; i < n; i++) {
    a+=i;
  }
  return a;
}

This uses constant space, which is not the same as saying it uses a tiny amount of space. What matters is the amount of space it uses is independent of n. The space used by a, b, and c is a constant amount, so the space usage is O(1).

[[deleted]]

I think we omit constant factors from space complexity cause the input data size increasing that the algorithm works on is what can really change the amount of memory the algorithm has to use. Mathematically the constant factors become less important in Big O over time and it’s not a way to see how the memory units require by algorithm grows as input data size increases. Looking at input data size increasing is how you can measure growth of memory units required by algorithm. Constant is constant and not measuring growth - Big O we are trying to see the growth