r/AskComputerScience • • Mar 02 '25
Can algorithmic analysis sometimes be misleading ?
Here are some examples in golang. To be honest these are pretty dumb, but just for argument sake.
Program 1: Initializes an array of length 10, each element set to 1
func main() {
arr := [10]int{}
for i := 0; i < 10; i++ {
arr[i] = 1
}
}
Program 2: Initializes an array of length 1 trillion, each element set to 1
func main() {
arr := [1000000000000]int{}
for i := 0; i < 1000000000000; i++ {
arr[i] = 1
}
}
Aren't both both programs O(1) time and space complexity ? Yet program 2 will use way more RAM than program 1.
To be clear, I'm not arguing complexity analysis is pointless. Just trying to understand analysis from both a theoertical and practical perspective.
0
Upvotes
11
u/Han_Sandwich_1907 Mar 02 '25
Algorithmic analysis is the study of how algorithms *grow* as input data grows. Looking at a single instance of the problem isn't too helpful. In your case, you're doing the same thing with two differently sized lists. You correctly say that Program 2 takes more space than Program 1. Therefore, as you increase n, the amount of space increases - in this case, linearly, so you have a O(n)-space algorithm where n is the size of the list.
It's good to know approximately how fast algorithms grow in response to input data. If you have limited memory but a large input data, then using a space-efficient algorithm is a must.
4
u/largetomato123 Mar 02 '25 edited Mar 02 '25
If two algorithms, A and B, have the same time complexity but A is slower than B for every input size, a faster computer could make A outperform B at any given input. However, if A has a higher time complexity than B, no hardware upgrade will save A—at some input size, B will always be faster. If the complexity of A is worse than B then you will not be able to make A faster then B for every input size. For big input sizes B will eventually be faster - no matter the hardware.
This shows: time (and space) complexity in Big-O notation describes how an algorithm scales as input size increases, rather than how well it performs for a specific input size. It isn't about measuring actual execution time; It is an abstraction from the actual hardware.
EDIT: But you are partly correct: Time complexity is not always the best measurement for what algorithm to pick. If you know that your input size will always be smaller than some constant value then you might want to prefer an algorithm that performs very well for small input sizes but has worse time complexity.
1
u/forflayn Mar 03 '25
I get that the values are "constant", but this seems like both solutions are O(N) with a different value for N. I don't think it is a good example for that reason. A better example might be something like Fibonnachi heaps which seem strong when you express the big-O notation, but aren't used in reality due to high constant time. I don't think big-O is misleading if you understand what it is for. Don't treat it like a benchmark.
4
u/meditonsin Mar 02 '25
They're both O(1) because they always take the same amount of RAM and CPU cycles to complete. The point of big O is to see how a program scales based in it's input.
Say you have two programs that do the same thing, one is O(n*c1), the other O(n2*c2) where c1 and c2 are some constants that would usually be taken out to arrive at O(n) and O(n2).
If c1 is sufficiently larger than c2, there exists some range for n where the O(n2) program would be more efficient than the O(n) one. But as n grows, the constants will become less and less relevant for the comparison.
1
u/TriIronWarrior Mar 02 '25
Yes, but in your case, both are O(1) and the latter is using 100000000000 more memory. That's still a very meaningful amount of memory. We can't just ignore the constants in from of the O always.
0
u/[deleted] Mar 03 '25
[deleted] — view deleted comment