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?
>>54580801
Yeah, try asking in a place not filled by 14 year olds.
>>54580801
Ciclomatic complexity
Uhh....I would say run it through a CPU and/or memory profiler?
>>54580812
I keep forgetting the intellectual maturity level of this board. I shitpost too but figured some people could be serious here and there.
>>54580812
fuck you im 15
>>54580801
This is covered in the first chapters of CLRS. Read a fucking nook
>>54580844
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.
>>54580836
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.
>>54580801
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.
>>54580895
Thanks anon. 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?
>>54580846
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.
>>54580801
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
>>54580905
Kek good luck if shit is more than 300 lines anon
>>54580962
I'm doing it less and less.
>>54580968
No I mean given some arbitrary program tell me the run time analysis of it
Look @ pic for an example.
>>54581001
Most of those 300 lines probably won't be relevant. You basically just look at the loop statements and any expensive function calls
>>54580968
> middle school
jesus, where did you go to middle school?
>>54581075
http://citc.ui.ac.ir/zamani/clrs.pdf
>>54581075
O(n)
O(1)
O(n^2)
O(n)
O(log n)
>>54581122
>http://citc.ui.ac.ir/zamani/clrs.pdf
Thanks taking a look
>>54581136
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.
>>54581165
Read that fucking book and you'll learn how. It's the same book I learned from
>>54581183
OK I'll start there then. Thanks.
>>54580948
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.
>>54581198
Cool thanks. I'm going to take>>54581165
suggestion and go through CLRS
>>54581198
Also, where did you get your white board? Been looking for one about that size.
>>54581241
Walmart
It was $20, and worth every dollar.
>>54581136
How'd you get O(1)?
>>54581299
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"
>>54580847
MOOOOOOOOOODS!
MODS MODS MODS!
>>54580847
MODS GET THE FUCK IN HERE
>>54580847
oh cool you'll fit right in
>>54581303
It always takes at most 50 steps to get count down to 0
>>54581303
Just count number of iterations thats all. If you know a number its O(1) no matter if its 50 iters or 1 trillion.
