Question about time complexity

[Peter87]

The point of my example is that keeping those constants and making judgements based on them is not an exact science. Sure, you could use them as a hint, but they could easily be misleading, and you would need to know what those numbers represent (so that you're not comparing apples and oranges).

If I were told the time complexity of two algorithms were O(1000n) and O(n²) without any further explanation I wouldn't know what to make of that. Especially if they came from different sources. What does 1000 represent? Is "the constant" for the second algorithm really 1 or has it simply been removed?

I think having 1000 loops is a bit unrealistic. In reality you would probably have smaller numbers making the numbers less reliable.

If two "unknown" algorithms had the same time complexity and I wanted to know which one is faster (for my use case) I think it would be more reliable to test both and measure.

[zapshe]

you would need to know what those numbers represent.

..what? They represent n iterations * constant. You can easily have a time complexity like this:

O(k*n) - like radix sort. In this case, k represents the largest sized number. The only reason it's not discarded is because its variable - changes based off the input. However, if you always knew that k would be, let's say, 1000.... it would become a constant for you and you'd have O(1000*n).

If I were told the time complexity of two algorithms were O(1000n) and O(n²) without any further explanation I wouldn't know what to make of that

If I told you I was gay and I wanted your number, you would think I was just being friendly?

[Peter87]

Note that even if you remove the constants from the Big O notation doesn't mean that the information is necessarily gone. You could still keep that information separate somehow, and add some explanation to help make sense of it.

[zapshe]

You may have missed my reply

[Peter87]

zapshe wrote:

..what? They represent n iterations * constant.

So the constant is the number of loops as before? I need to be told this because it's not the only interpretation.

I think more accurately would be to count the number of basic (elementary) operations.

https://en.wikipedia.org/wiki/Time_complexity

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

That would mean I could do 10n operations by using one loop from 1 to n that does 10 basic operations per iteration, or I could use two loops from 1 to n that does 5 basic operations per iteration. There are of course many other alternatives to get the same number of operations.

If you used your way of counting and I used my way of counting they wouldn't be comparable.

Counting things in this much detail is quite a bit of work and usually not worth it. Using Big O and throwing away the constants makes it much easier.

zapshe wrote:

O(k*n) - like radix sort. In this case, k represents the largest sized number. The only reason it's not discarded is because its variable - changes based off the input. However, if you always knew that k would be, let's say, 1000.... it would become a constant for you and you'd have O(1000*n).

I'm no expert on radix sort, and there seems to be different variants, but my understanding is that it loops over the input array multiple times for each digit and the choice of radix is also important.

I think k is actually the length (i.e. the number of digits) of the largest number. So if the largest number is 1000 then k is only 4 when using a radix of 10 (i.e. counting digits using our normal 10-based system). If we use a radix of 256 (i.e. using bytes as our "digits") then k is only 2.

But using larger radix means it has to do more work for each "digit" so if you want you could probably think about it as O(k×(n+r)) where r is the radix.

[zapshe]

So the constant is the number of loops as before?

The constant is just a constant. If you know that your loop will iterate twice per array value for example, then you have O(2n), and then you simplify to O(n).

I need to be told this because it's not the only interpretation.

As far as I know, this is the only interpretation.

On the same wiki:

An algorithm is said to be O(1) constant time if the value of T(n) is bounded by a value that does not depend on the size of the input

If you have a program that runs the same no matter the input, its O(1). Time complexity is about how many iterations per input. You can have 1 iteration per input O(n), or squared iterations per input O(n^2), etc..

The constants have nothing to do with any particular elementary operations.

The wiki article is simply misleading, as looping can be considered an elementary operation (goto).

I think k is actually the length (i.e. the number of digits) of the largest number

Yes, I said the largest "sized" number.

So if the largest number is 1000

I didn't mean the largest number is 1000, but that the largest number contains 1000 digits.

But using larger radix means it has to do more work for each "digit" so if you want you could probably think about it as O(k×(n+r)) where r is the radix.

I'm not sure what you're talking about.

Radix sort, as I know it, sorts the first place digits of all the numbers, then the 2nd place, and so on. So it iterates n times to sort, but it also does that for every digit - hence k*n.


Again, the k value is usually very small, but since its entangled with the input, it's part of the time complexity. Every bit of information is important when accessing algorithms.

[Peter87]

If you come up with an expression that describes the number of elementary operations (e.g. in the average or worst case) as a function of the size of the input(s) then when you put that inside the Big O notation and remove all constants and non-dominant terms you get the time complexity as expected.

Example:

int get_sum(int arr[], int n)
{
	int sum = 0; // +1
	
	for (int i = 0; /* +1 */ i < n; /* +(n + 1) */ ++i /* +n */)
	{
		sum += arr[i]; // +n
	}
	
	return sum; // +1
}

I have put the elementary operations count in comment after each statement.

So the total number of elementary operations are 1 + 1 + (n + 1) + n + n + 1 = 3n + 4.

If we express this using Big O time complexity we get O(3n + 4) = O(n).

We could always discuss how exactly we should count the number of elementary operations (should += count as two, should array indexing be counted separately, etc.) but if we are only interested in the Big O time complexity it doesn't really matter as long as they are O(1) operations.


Normally we would not do it this way. We know from experience that we should focus on the loops and when we have a non-nested loop like this we can easily see that it's O(n). But when you start to talk about not throwing away information it feels strange to me because we're "always" throwing away this kind of information. Just counting the number of loop iterations works but by doing that you have already thrown away a lot of information. To me it seems a bit arbitrary which information is kept and which information is thrown away. It seems like the thrown away information might very well be equally or more important than the information that we keep. That's why I feel it's pointless to try and keep any of this extra information when dealing with Big O. If we are interested in it we can just count it separately and describe what it means properly.

I don't think there is much more for me to say.

[zapshe]

O(100n) would mean you loop 100 * n times, not 100 operations then n loops..

[Peter87]

OP before post got deleted wrote:

What are you guys talking about ???? I'm very confused ????

O(n), O(2n), and O(521564n + 7) all mean the exact same thing.

The disagreement is about whether it's sometimes useful to not write it using the simplest form.

I say it isn't. The other person say it is because he attach additional meaning to those numbers.

[Duthomhas]

It’s a <adjective-deleted> disagreement because both thoughts are correct.

It is useful to know something about the actual performance function of your algorithm.

Big-O notation doesn’t care about that. It only cares about the amortized performance. To amortize something is to write off (or ignore) the initial costs of something over time. In the case of a function like this, that is any cost that becomes insignificant for sufficiently large N (like infinity).

That is why we can say that (2n + 7) is the same as (n). For any big enough value of n the difference means nothing. (What’s the difference between 2n+7 and n if n==300? About nothing. What if n==300,000,000,000? In terms of computing, you are likely to hit other problems before that coefficient becomes an issue.)

The way to figure out which terms become amortized (i.e. become insignificant as “time” spent processing larger and larger n) it out is to consider which term becomes dominant for large n. This requires a little basic Calculus. We are looking for the limit as n ⟶ ∞.

Which term dominates?

    n + 3n + n²

    logₑn + n·logₑn

    nⁿ + n·log n

And now for some tricky ones: which term dominates?

    log₂n + log₁₀n

    1/n² + 500n

    n^n/2 + n·n

The purpose of Big-O notation is to generalize an algorithm’s behavior for some unknown but sufficiently large (i.e. “big enough that it matters”) value of n.

It does not obviate the utility of having a more exacting performance function describing an algorithm. That is, both measures are useful.

Know your data.





Answers

<sub><sup>1. term 3
2. term 2
3. term 1
4. neither term
5. term 2
6. term 1</sup></sub>

[zapshe]

It’s a <adjective-deleted> disagreement because both thoughts are correct... It is useful to know something about the actual performance function of your algorithm.

The issue isn't whether Big-O should or shouldn't simplify algorithms, it's about whether a programmer would be able to extract more information from O(100*n) vs O(n). He claims that the 100 would be useless information that tells you NOTHING.

[Duthomhas]

me: <both hands up, empty> <backing slowly out of the room>

[zapshe]

LMAO

[George P]

This is one of the politest "flame-wars" I've seen in quite some time. :Þ

The more the "The One True Way" debate over O(100*n) vs. O(n) rages on the more I really find my ability to care goes on sabbatical.

Yeah, I may be just a simple hobbyist programmer, this disputation is a great insomnia antidote.

[zapshe]

I just can't understand the logic of giving yourself less information to work with.

This is one of the politest "flame-wars" I've seen in quite some time. :Þ

I'm sure the next one will excite you <3

[Peter87]

After rereading some of the discussion I think that the following quote might be the root cause of our disagreement.

zapshe wrote:

Time complexity is about how many iterations per input.

And based on this I can understand if you're tempted to read the expression inside the Big O notation to mean the number of loop iterations. E.g. 2n is two loops from 1 to n (or one loop from 1 to 2n?)

But I think this is a misconception. Instead time complexity says something about the time it takes to run an algorithm. To estimate this we can count the number of elementary operations (like I did in an earlier post https://cplusplus.com/forum/beginner/284474/2/#msg1232098).

Counting the number of loop iterations (or recursive steps) works most of the time but it's not what time complexity is all about. It just happens to work because the "constants" that describe how much work is done in each iteration and elsewhere can be ignored with Big O.

[lastchance]

Another way of looking at it is if you have an O(N²) algorithm then doubling N will (roughly) quadruple the time taken. It is the ratio of times that will allow you to decide whether an algorithm that you have timed for small N is likely to be practical for large N.

Putting constants like 100 inside the O() relation is not particularly helpful: some operations (+,-) will usually be much faster than others (*,/) or expensive math functions like exp() or tan(). The actions of a good optimising compiler can obliterate the effect of constant multipliers.

[zapshe]

But I think this is a misconception

How so? Specifically speaking, Big O notations refers to how many times you go through a certain set of operations per n value.

If you don't loop or have recursion, you're always going to have O(1). The specific number of operations you go through per n value doesn't matter.

It just happens to work because the "constants" that describe how much work is done in each iteration and elsewhere can be ignored with Big O.

THIS seems to be a misinterpretation of Big O. For example:

for(int i = 0; i < size; i++)
{
    //1 line of work;
    //another line of work;
    //a 3rd line of work;
}

This is NOT O(3n), this is O(n). You are NOT saying you're doing 3 lines of code per n value, you are saying you are going through ONE SET of instructions per n value.

for(int i = 0; i < size * 2; i++)
{
    //some work..
}

This would be O(2n), simplified to O(n). Though you can clearly see it would do twice the amount of looping of O(n).



From https://stackoverflow.com/questions/33269159/c-what-does-on-mean:

O(n) means, in a cycle of n iterations, for every n there is only a single algorithmical step to be taken

For every n, there's a single algorithmical step, not a single operation - but the combination of operations that make up your algorithm.


Hence, O(100n) would mean you go through your algorithm 100 times for every n value - through a loop or recursion. This is STILL linear, so it's simplified to O(n). However, clearly, there is information to be extracted from the constant.

This is also why radix sort is O(k*n). The "k" is not a constant hence not removed. And k being the digit-size of the largest number means you'll LOOP n*k times.

The actions of a good optimising compiler can obliterate the effect of constant multipliers.

Not helpful because of compiler optimizations or because the constant itself cannot tell you anything?

[lastchance]

@zapshe, are you sure that you aren't related to @frek?
https://cplusplus.com/forum/general/284338/#msg1232306

[zapshe]

@zapshe, are you sure that you aren't related to @frek?

Ah yes, my alter ego. My sham has been thwarted! Damn you lastchance!

But no. And I haven't needed help with coding problems for years now. This is my only cplusplus account.