I'm familiar with proving big oh, etc. but I haven't came across any resources that provide a general rule of thumb for analyzing program complexity of actual code.
if someone asked me what the run time of an arbitrary program is I'd like to know how to figure it out.
Any resources that explain this or any general rules of thumb?
Other urls found in this thread:
Yeah, try asking in a place not filled by 14 year olds.
Ciclomatic complexity
Uhh....I would say run it through a CPU and/or memory profiler?
I keep forgetting the intellectual maturity level of this board. I shitpost too but figured some people could be serious here and there.
fuck you im 15
This is covered in the first chapters of CLRS. Read a fucking nook
I am wondering how to figure of bounds on the complexity being language agnostic.
For instance if it has 2 loops and x,y,z then you could somehow say the program runs in O(n^2) time.
I'm not sure what the general method to determine this is.
A-are you actually retarded? I mostly use that as a phrase, but this time, I really mean it.
I might be wrong, but I would just analyze what each block of the program does. For example, if you have n elements in an array to loop through and do operations on each each element, you know it's n time, times some constant for the operations (assuming the operations don't call other blocks of code that take up more time).
For recursive procedures you can analyze best and worst case scenarios, as well as determine the time taken for each call.
I would like to think there's an algorithm for analyzing a program to determine its O time, but if there is I don't know it. Hopefully someone else can provide more information.
Flowchart and pseudocode.
As simple as these two are, if you familiar with them, you basically already has the structure in your head. Shit codemonkeys/pajeets always disregard them and writing shit on a whim, so long as it runs and can be compiled
You can also approximate the complexity quite well by measuring time in relation to the input size.
Thanks user. What do you look for in worse case with recursive algorithms? Let's take Fibonacci sequence for instance. Pretend you never seen it before and need to analyze the run time for the very first time. What is your general approach?
You're part of the problem. I remember a time when most people weren't brazen enough to describe themselves as shitposters. I certainly wouldn't use that word to describe any of my posting habits.
It's literally just middle school algebra. If code with complexity o(1) is called n times, n*1=n. It's that easy.
If code with complexity n is called n times, n*n=n^2
Kek good luck if shit is more than 300 lines user
I'm doing it less and less.
No I mean given some arbitrary program tell me the run time analysis of it
Look @ pic for an example.
Most of those 300 lines probably won't be relevant. You basically just look at the loop statements and any expensive function calls
> middle school
jesus, where did you go to middle school?
O(n)
O(1)
O(n^2)
O(n)
O(log n)
>citc.ui.ac.ir
Thanks taking a look
How did you come up with those? That's what I'm asking for the thread. I'm trying to self-study so not learning this from a class.
Read that fucking book and you'll learn how. It's the same book I learned from
OK I'll start there then. Thanks.
I have an engineering background so I think more about the hardware side of things. My first approach would be to do a stack trace of the algorithm. I don't know if this is more or less work then trying to work out the time complexity in terms of O time. I use this approach to optimize algorithms in my programs rather than determine exact complexity. There may be a way to get O time from this approach and I'm just not seeing it, but it gives me a good idea of how efficient a given algorithm is.
Cool thanks. I'm going to take suggestion and go through CLRS
Also, where did you get your white board? Been looking for one about that size.
Walmart
It was $20, and worth every dollar.
How'd you get O(1)?
Thanks man.
I always think can i put this part in a self commented function?
but the simple rule of thumb is more then 4 levels of indentation "you fucked up"
MOOOOOOOOOODS!
MODS MODS MODS!
MODS GET THE FUCK IN HERE
oh cool you'll fit right in
It always takes at most 50 steps to get count down to 0
Just count number of iterations thats all. If you know a number its O(1) no matter if its 50 iters or 1 trillion.