Is this thought process correct?
int fac (int i)
if i < 1 // O(1) |+
return 0 // O(1)
else if i == 1 // O(1) |+
return 1 // O(1)
else
return i * fac(i - 1) // O(n)
} // => O(max(O(1),O(1))+O(n))
= O(n)
while (n >= 1) { // O(n)
n = n/4 // O(1)
instr with f(n) // O(f(n))
} // => O(n)+O(1)+O(f(n)) = max(O(n),O(f(n))
>>54502041
>not using code brackets
can't even read m8
use code tags
>>54502041
> O(n)
> O(n)*O(f(n))
int fac (int i) {
if i < 1 // O(1) |+
return 0 // O(1)
else if i == 1 // O(1) |+
return 1 // O(1)
else
return i * fac(i - 1) // O(n)
} // => O(max(O(1),O(1))+O(n))
= O(n)
while (n >= 1) { // O(n)
n = n/4 // O(1)
instr with f(n) // O(f(n))
} // => O(n)+O(1)+O(f(n)) = max(O(n),O(f(n)) >>54502166
>still using big O
Shiggymydiggy
>>54502166
Only choices count, or so I've heard.
>>54504369
you heard wrong
>>54502041
>>54502166
Nope, that thought process is incorrect. Are you smoking meth?
>>54502166
>>54504369
>>54504459
Eh, it depends on what you're measuring.
O is an abstract notation that just gives you some way of categorizing the growth behavior of an arbitrary function. In itself it has absolutely nothing to do with performance or memory usage or anything.
But you can use it to talk about exactly those things. For that, it depends on what exactly you're trying to capture.
For example, in a claim like “This sorting algorithm will perform O(n) pairwise comparisons”, then only the number of comparisons matters.
In a claim like “This algorithm will perform O(n) integer multiplications”, then only the number of multiplications matters.
When the exact quantity you're counting is left away, it's generally taken to mean something vague like “atomic instructions”, where an atomic instruction is anything that runs in some small fixed amount of time. (For example, doing a comparison, or performing a branch, or adding two fixed-width integers)
Special care needs to be taken to distinguish between bit complexity (for theoretical algorithms running on unbounded inputs) and integer complexity (for real-world algorithms running on fixed integers). In the case of the former, you're generally counting the number of bit operations (e.g. gate evaluations) that need to be done.
Or the number of state transitions in a turing machine. Or whatever.
>>54504459
I heard that from the guy who interviewed me for a developer job. I had a feeling he's wrong because he gave a very simple Big-O notation for my complicated recursive function.
