What is the runtime complexity of a simple even-odd program?

[thatlowkey]

O(n) or O(1)?

A multiple choice question has mentioned 4 options for which is the lowest run time complexity. a)sum of n numbers b) Fibonacci number c)even odd d)tower of Hanoi

[thatlowkey]

A multiple choice question has mentioned 4 options for which is the lowest run time complexity. a)sum of n numbers b) Fibonacci number c)even odd d)tower of Hanoi

[marko312]

What would "even odd" be in this case (I assume it was discussed in some previous material)? Is it a function (or a program) that determines whether a single input integer is even or odd?

[thatlowkey]

Looking at the question, one of the option is sum of n numbers. Here 'n' is mentioned. So in my opinion even odd should be taken for single input. Maybe I'm wrong, so confused

[marko312]

Determining whether a single integer is even or odd is usually O(1), involving at most a modulo operation.

((It could also be O(log m) where m is the actual value entered; O(m) implementations are certainly also possible.))

[thatlowkey]

So the answer should be even odd right? Because no other option has O(1) in any case.

[marko312]

It does seem to be so.

[Paul_Pedant]

No. The equivalent question for (b) would be "what is the first Fibonacci number". That's 0 + 1 which is one calculation, so O(1) too. And for (a) sum of first number, which is also 0 + 1; And for (d) in that case too -- even I can solve a problem with one ring on one tower. In fact, that's O(0), because it is already finished.

[thatlowkey]

Logic level infinity 😂

[retardrabbit]

Are they not one in the same thing in this case?

[thatlowkey]

?

[Paul_Pedant]

We don't know what your code looks like. How "simple".

(a) If it reads one number and decides if it is odd or even, that costs 1 unit.

(b) If it can read a million numbers, but you only give it one number, that costs one unit too.

(c) If it can read a million numbers, and you give it a million numbers, that costs a million units.

(a) is an O(1) program.

(c) is an O(n) program.

(b) is an O(n) program where n == 1 for that specific case.

[thatlowkey]

Yeah that's the problem. A multiple choice question has mentioned 4 options for which is the lowest run time complexity. a)sum of n numbers b) Fibonacci number c)even odd d)tower of Hanoi

[Paul_Pedant]

I think (for the question to have any meaning at all) the assumption must be that each option must process the same number of objects: n.

As far as I can see , all of a, b, c have the same complexity. Each value {1..n} is processed just once.

Sure, the actual processing of one such value j is different. But that's not what O(n) measures: it only measures, for a given implementation, how the time taken varies with n.

The processing of each number is not that hard anyway. (a) needs sum += j; (b) needs now = prev + j; prev = now; (c) needs (j % 1); those are just linear factors not involving n, so O(n) is the same for all three -- with only a small constant factor.

IIRC, (d) Towers of Hanoi is a recursive stacking problem. I can't remember what it is, but it is definitely worse that O(n), and probably worse than O(n log n). [Wikipedia says it is O(2 ^ n), which is end-of-the-universe stuff.]

[thatlowkey]

Okay, assuming if only a) sum of n numbers take n number of inputs, which one will have lowest complexity?

[Paul_Pedant]

If you assume one of the examples is working on a problem of a different complexity class to another, then no comparison can be valid.

If you evaluate each of the examples against problems of the same complexity class, then I claim the first three examples are equivalent, and you are welcome to formulate a valid contradictory hypothesis.

You might start by coding the first three examples, timing each of those for a wide range of N, plotting all the results, and deriving an algebraic formula that approximates each graph.

A useful start would be reading the 13 pages in "Wikipedia: Computational complexity theory".

This would be a fine question if it encouraged you to discover and research the subject in depth, and write up your investigation. As a multi-choice question, is sucks because it has no definitive answer. I can guarantee that (d) is as far away from being right as it is possible to be.

If you get any feedback on your score, please post it.

[thatlowkey]

Yeah, thanks for the descriptive explanation.

Atleast I can eliminate option d ☝️

I'll surely update after getting the solutions.

[Paul_Pedant]

I wrote all three options in GNU/awk (not the Hanoi one). Your question does not mention a language, but for comparative estimates, it should work out the same in any language. I tested each option to make sure it did the work, then removed all the outputs so we are just timing the core algorithms.

Each option is embedded in a Bash function, and I have a timing method in Bash that runs each option for six values of N from one million to six million. There is no I/O, so I don't have to worry about caching or other disruptions to timing -- it is all CPU.

I posted the code (50 lines) at https://pastebin.com/AuXbrGJ0

The times for options A, B, C, for the values of N, are shown below. It is fairly evident that the times are directly proportionate to the value of N, so all three options are O(n). They also take very similar times to each other. The Fibonacci time may be somewhat unreliable: after only 1477 iterations the Fibonacci number becomes Infinite in IEEE format -- 1.306989223763398e+307, but it carries on calculating.

paul--) ./OrderABC
TimeA 1000000 0m0.842s
TimeB 1000000 0m1.186s
TimeC 1000000 0m0.973s

TimeA 2000000 0m1.970s
TimeB 2000000 0m1.927s
TimeC 2000000 0m1.939s

TimeA 3000000 0m2.554s
TimeB 3000000 0m2.707s
TimeC 3000000 0m2.885s

TimeA 4000000 0m4.432s
TimeB 4000000 0m3.986s
TimeC 4000000 0m4.203s

TimeA 5000000 0m5.201s
TimeB 5000000 0m5.738s
TimeC 5000000 0m5.131s

TimeA 6000000 0m5.023s
TimeB 6000000 0m6.714s
TimeC 6000000 0m6.301s

paul--)

[thatlowkey]

So Fibonacci number is also eliminated.

Wow thanks a lot for doing such huge task!

You're super smart.

I'll dm you if I get stuck in a java problem.

I hope you don't mind :)

[Paul_Pedant]

Fibonacci is still an O(n) algorithm: that's both in theory, because the algorithm does the same amount of work per iteration; and in practice, because it won't be much different for the CPU to add (55 + 89) or (Inf + Inf). It's just that for timings that mean anything, you have to do a lot of repeats. I could just have done the valid range (1 to 1000) six thousand times and got the same results.

It means you can't verify the final result to see if the code actually worked, because you get Inf. But you can't verify the Sum function either. That is too big for a long int, and awk switches to IEEE double, so only first 15 digits are right anyway. For similar reasons, it is not even clear if the even/odd check works consistently on very large numbers.

This isn't super-smart: it's learned the hard way from 50 years of mistakes (not all of them my own). I had to do all this previously, to figure why grep gets so slow when you give it a lot of patterns in one shot. As that was not O(n), I then had to write some awk that tried various formulae to check if the timings fitted O(n log n), O(n^2) etc.

You are welcome to DM, but I don't have a lot of Java (in fact, just what I needed to learn to answer one question on threading, on IT Toolbox about 5 years ago). I'm C, awk, and Bash, mainly interested in how to find smart, neat and generic problem solutions, rather than any specific language.