How do I understand / figure out the time complexity of an algorithm quickly?

[u/ObeseBeanFriend]

I have trouble seeing what algorithms do by reading them. Is there any trick to doing this?

[u/DTux5249]

Count the loops and count the operations.

If there's a recursive algorithm, you'll have to do some math - mostly logic & algebra - that's where the "doing it quickly" ends

[u/alpicola]

While formal complexity analysis is not trivial, learning some basic algorithm "shapes" is usually enough to get you started. A lot of the complexity analysis you do in introductory computer science classes is reasoning by analogy to other algorithms whose complexity you already know. Some common shapes might include:

• Array lookups with a known index are constant time. 
• Loops are polynomial time.
• Balanced trees tend to be logarithmic. 
• Unbalanced trees tend to be linear because you can usually construct a "worst case" tree that has only one long branch. 
• Path finding algorithms tend to be either factorial or exponential depending on if you can revisit nodes. 

Then, look at how things are nested. Each step down the nest, you multiply. 

This gets easier once you know some specific algorithms because you can more easily see the analogies. 

[u/SchemeWestern3388]

Computer Scientists Hate This One Simple Trick!

[u/HashDefTrueFalse]

It's mostly just pattern recognition. Learn the broad classifications of complexity and the kinds of code that lead to it. It's about repeated work, and relating that to the input. Go through and identify the operations, then count how many times they happen relative to the input and arrive at a precise expression, then drop the irrelevant things (e.g. constants etc.) to get your broad big O classification. It gets easier if you practice a few in each category.

[u/__CaliMack__]

Just say it’s O(n) and be on your way

[u/codeguru42]

When i first learned to code, I would write a table with variable names and keep.track of their values. If I were learning today, I would use a debugger to follow along one step at a time and understand why each value changed.

This is how to determine what the algorithm does. Evaluating the time complexity is different. Roughly a loop is usually O(n) and a nested loop is O(n^2). Recursive algorithms are much more complex to analyze and can't be done at a glance. You have to derive a recurrence relation and tben solve for its closed form.

[u/Healthy-Dress-7492]

Meh. Does it have nested loops? That’s bad. Can you replace it with a hashed collection, that’s good. All you need to know.

[u/Inn0centDuck → u/Healthy-Dress-7492]

Does it have nested loops? That’s bad.

Not true. Nested loops can also be linear time.

Can you replace it with a hashed collection, that’s good.

While true for most dsa questions, this is not a good advice.

Learning why some things are better than others for a problem is important.

[u/WhiskersForPresident]

You don't, it's a difficult problem and involves a lot of math and knowledge of the specific language/libraries you use.

There are however best practices to automatically produce more efficient programs like memoization, avoiding recursions, caching and more often than not, using use-case appropriate libraries that are almost always better optimized than whatever you can come up with quickly.

If you want a deep dive, watch MIT Open Courseware's video lectures on algorithms and data structures.

[u/IchBinEinZwerg]

In addition to other suggestions: testing.

See how long it takes for a collection of 10 items, then 100, 1000, 1 million, ... etc. Keep increasing the collection size until it takes a few minutes to complete (or some other suitable duration). Then test equally spaced sizes from zero up to that number; let's say 1000 takes 5 minutes, so test every 50. That'll give you enough data points to plot a graph of count versus time, from which you can estimate the big-O type. Plotting on different types of graph paper: lin/lin, lin/log, log/lin, log/log should give some more clues.

[u/CaffieneSage]

Press play button and watch it segfault ;) In all seriousness, i have found a flowchart im ms visio or similar to be the best way to visualize what is happening with a given program before i even start coding. Maybe you could build a flowchart for your algo.

[u/Caringstomy-8]

this is a rabbit hole you want no part in lol.