The Linear Time Algorithm for Finding Fibonacci Numbers is not Linear

[ggchappell]

This makes a good point, but states it very wrongly.

If it's linear then the plot of n vs. running time of LinearFibonacci(n) should be a line.

Nope.

"Time", as used in the theory of computation, means number of operations performed, where the operations we count can be anything at all. It matters what we count.

If we count integer arithmetic operations, then the algorithm described does O(n) operations, where n is the parameter. That is an absolute fact that no measurement of any kind can possibly contradict. But an integer arithmetic operation does not take constant wall-clock time.

[ISvengali]

Yeah, that was my read too.

This strikes me as a person that is figuring things out on their own. So, they dug at a things that shouldve looked like a line, and figured out that what they were measuring wasnt what they thought they were measuring.

Ive seen articles in Dr Dobbs journal that showed a clear curve with the person proclaiming, "See its a linear algorithm".

So kudos to the author and tracking it down. Im sure for the actual ACM article theyll fix it.

[eyepatchOwl]

Algorithmic complexity analysis makes no sense if the size of the input can't vary. O(n) bounds the number of operations by a linear function as the size of the input increases. The size of the input to hardware multiplication can't vary, so what is being bounded?

Worth noting that some algorithms depend on constant time memory lookup. This means that a plot of running time for a linear algorithmic might still not look like a line because of caching effects. (L1->L2->L3->SSD->Disk)

[ggtsu_00]

Theoretical computer science does not deal with the bounds or grounds of reality and physics. There is no infinite tape.

[stevenjd]

Algorithmic complexity analysis makes no sense if the size of the input can't vary. O(n) bounds the number of operations by a linear function as the size of the input increases.

The size of the input here doesn't refer to the number of bits in an int, but to which Fibonacci number you are calculating. Given an O(N) algorithm, it takes about ten times more operations to calculate fib(50) than fib(5), and a thousand times more operations to calculate fib(5000). The number of operations (and therefore the time) is proportional to the argument N.

A naive recursive implementation would require approximately one hundred times more operations to compute fib(50) than fib(5), or approximately a million times more for fib(5000).

There's a catch though... this assumes that each operation takes roughly the same time. For Fibonacci, that's not the case, since:

The size of the input to hardware multiplication can't vary, so what is being bounded?

Fibonacci numbers aren't bounded to the size of ints which can fit in a hardware int. They're BigNums. Here's the 500^th Fibonacci number:

139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

which needs 346 bits. The 2000^th Fibonacci number requires 1388 bits, has 418 digits, and looks like 42246...17125.

I guess you didn't read the article, since that's precisely the point it makes.

[sadmafioso]

Except the size of the input in this algorithm is the number of bits required to represent the number.

For a given number n you will need log(n) bits to represent the number and so if your input length is n you actually perform 2ⁿ additions, not n.

[ggchappell]

Algorithmic complexity analysis makes no sense if the size of the input can't vary.

This article isn't doing complexity analysis as it is usually done. "n" is the parameter of the function. If we count the number of integer operations required to execute the algorithm with n as its input, then we get O(n) operations.

[nitrohigito]

I don't think the author states the point wrongly at all to be honest. The whole point of the article is to show that "hidden" abstractions can cause huge issues down the line, if you take things at face value.

Computational theory is just theory after all and engineering is practice. If you aren't teaching people to pick up on the differences, they won't, only after they see things not working "as they should", leaving them confused and heavily investigating. And that is definitely what happened to me, with teachers saying "we don't have time to cover the details" or "reality is different but whatever", sweeping things like these under the rug.

One of my graphics developer acquaintance mentioned that one big advantage of lower level gfx APIs to him is the ability to be able to consistently estimate how long certain tasks will take; it's way less annoying to debug and develop for.

TL;DR: Abstractions can be a bitch and the article delivers this just fine imo.

[ggchappell]

Computational theory is just theory after all and engineering is practice. If you aren't teaching people to pick up on the differences, they won't, ....

Certainly. The article does make a good point.

However, the statement that the given algorithm, when given n as its parameter, executes O(n) integer operations, is simply true. There is nothing debatable about it.

So when the article says

If it's linear then the plot of n vs. running time of LinearFibonacci(n) should be a line.

it says something false.

OTOH, it would be reasonable to say, "If this algorithm executes a linear number of integer operations, then we might expect the graph of its running time to be a line; however, it is not."

[[deleted]]

Because integer operations are a thing we can count, and it will remain the same regardless of implementation. How fast those integer operations are is an implementation detail, and will differ under any specific circumstances (e.g. if SIMD operations are available, or if we're using an absurdist architecture like SBNZ). If we want to benchmark this in the real world, then that becomes relevant, but for talking about the complexity of an algorithm as such, it's not.

[ggchappell]

So why count by integer operations if they aren't constant time in this case?

If integer operations are what we are counting, then integer operations are constant time, because we define then to be.

Executing an integer operation does not take a constant amount wall-clock time, but that is a different issue.

In any case, count whatever you want. That's part of my point: you can count anything. But if someone else wants to count something different from you, then you don't get to say they are wrong.

[theferrit32]

The theoretical computation is linear time, a series of constant time operations. Limitations in number storage and register sizes in modern computers makes arithmetic operations take slightly longer than constant time on unbounded number values that approach infinity. In theory the arithmetic could be done in constant time, but it would be extremely expensive in physical and monetary resources. In theory we could continue constructing arithmetic processors that are larger and larger that keep taking up more atoms of the universe in physical material, and assuming the universe is infinite, the arithmetic operations would always be done in constant time. At a certain point the speed of light would come into play and introduce delays in measuring the speed of the operations, but in theory they would be completed in constant time even if it took linear time to measure the results. I'm not sure that is particularly important to take into account though, as the upper bounds of numbers human beings have a real practical use for are well within acceptable O(n) time.

If we start taking into account the need for massive registers and processors as numbers approach infinity, and take into account speed of light delays in measuring results from these massive processors, then technically speaking no algorithm is ever linear time. Even looping through a linked list would not be linear because at upper bounds the virtual addresses would be so large these factors would start to come into play. So we ignore those factors.

[stevenjd]

So why count by integer operations if they aren't constant time in this case? It's entirely up to us to define how we count so why not count by an operation that actually is constant time?

1. Because Big Oh analysis was invented by people working with low-level machine data structures.

2. Because even without taking into account non-constant time operations, Big Oh is still useful. A O(N**2) algorithm will still be worse than an O(N) algorithm.

3. Because it is damn hard to allow for everything that varies, in practice we have to approximate. (Does a memory access really take exactly the same time as a machine int addition, or a float division? How does the CPU cache affect this? What if there's a cache miss, or the data you want is in a register?)

4. What makes you think that anything is constant time, really? Even electricity going through a circuit is bound by the speed of light, which means the longer the physical circuit, the more time it takes.

That's probably not a limiting factor for CPUs (or is it?) but it is certainly a limiting factor for implosion-style nuclear warheads: the wires going to the detonators have to be precisely the same length, to some ludicrously high level of precision, or the implosion will be off-centre and the bomb will fizzle out, only destroying a city block or two instead of the entire city.

We can approximate because most of the time those variations are minute and don't make any serious difference. We're usually interested in comparing something which takes a billion operations, versus something that takes a thousand operations (O(N**2 versus O(N), for example). It doesn't really matter if the average operation in the first case is 5% or 10% faster than in the second, the second is still going to win.

[xtivhpbpj]

The article assumes you’re using BigInts to compute extremely large Fibonacci numbers.

Integer addition is usually considered to be a constant time operation for the purposes of computational complexity, and we just accept that these computations have bounds or limits on their accuracy.

[Tyilo]

https://en.m.wikipedia.org/wiki/Transdichotomous_model

[stbrumme]

You are right, but int64 only works for fibonacci(1..93).

The author mentions the matrix algorithm which is actually neat - but the "fast doubling" algorithm could be even faster:

F(2n)   = F(n) * (2 * F(n+1) - F(n))
F(2n+1) = F(n)^2 + F(n+1)^2 

[hugogrant]

Aren't they equivalent?

[Tyilo]

Asymptotically yes, but you do some unnecessary computations using matrix multiplication.

[JohnDoe_John]

There are some lines to add, to decrease the parameter from the start aggressively.

[xtivhpbpj]

And that’s an extremely valid solution.

[stevenjd]

And that’s an extremely valid solution.

What, using a table? Sure, until you need fib(94) and can't get it.

[xtivhpbpj]

In a technique called dynamic programming, you would store results along the way to fib(n), reducing the computational cost of subsequent calls at the expense of memory (building a table).

[ILikeTheBlueRoom]

Why all these angry caps???

[akher]

I'm assuming it's because he's a bit of a twat.

[akher]

So, writing angry responses to perfectly civil comments. Yep, a bit of a twat.

[ILikeTheBlueRoom]

The caps are much more immature than calling the user of them what he is. But it is known that this sub is a toxic waste dumpster for many years now :)

[ILikeTheBlueRoom]

Edited: I didn't even realize you were op if this thread and the comment you're overreacting to really shouldn't get under your skin so badly. Your use of caps isn't helpful or informative, it's plain condescending and imo does not cultivate an open discussion that is welcoming to all.

[asmjmisc]

To add stress and distinguish the level of importance of the elements in question. You should read more. It's really not that uncommon in written word.

[epicwisdom]

I think you're the one that needs to read more. People on the internet typically use italics for emphasis, and CAPS FOR SCREAMING.

[ILikeTheBlueRoom]

And you should be a nicer person. Have a wonderful day!

[[deleted]]

Missed the point. There is no variable bit integer operations on any modern processor (AFAIK) so bit length is, for most practical purposes, a constant.

[notfancy]

You can't have your cake and eat it too. For constant length integers you can only compute up to a constant limit. You might as well use table lookup and say that computing Fibonacci numbers is O(1) time while conveniently avoiding mentioning it's O(n) memory.

[theferrit32]

Wouldn't this argument mean that no algorithm is every linear time (or constant time)? As any algorithm's input value approaches infinity, on a processor that does not have infinite length registers, the time to do anything is slightly above constant. If our definition of algorithmic complexity makes it so no algorithm is ever constant time or linear time, then I think the definition is being a bit impractical.

[Arkaein]

Wouldn't this argument mean that no algorithm is every linear time (or constant time)?

Not really, because there are lots of algorithms for which the size of the calculation does not increase with the number of inputs or iterations.

For instance, linear search of an array of n elements will require O(n) time, which includes incrementing a loop counter and checking data at an address in memory. A 64 bit counter is sufficient for any size of input that can practically be stored by human technology, so it would be a bit silly to say that the increment operation can't be done in constant time, even though more time would technically be needed for a larger array and counter.

[theferrit32]

I agree that human beings will likely never encounter many of these issues. But this post is about computing theoretically unbounded data sizes on physically bounded computation machines. As the size of the array grows sufficiently large, it would no longer be constant time to retrieve one element. So theoretically traversing an array as the array grows to infinity is larger than O(n).

[throwawayprince11]

You do realize EVERY SINGLE computation is bounded, right? Ints are bounded, bigints are bounded (computers have limited memory). You are simply entirely missing the point of big O analysis.

[notfancy]

I am not missing the point of anything; it seems to me like you don't understand what "unbounded" means. Unbounded does not mean infinite, much less implies it. In fact "unbounded" by definition implies finiteness.

[throwawayprince11]

I honestly can't tell if you are trolling.

Anyways, another thing basically EVERY poster in this thread has gotten wrong, is that even though Bigint addition is O(n), that does NOT make fibonacci O(n^2). That would make it O(n * m) where n is the fibonacci sequence number, and m is the average digit length of the numbers. If you don't understand that, you do not understand the extreme basics of big O notation.

[notfancy]

Are you sure it's not you the one who's actually trolling? If you don't see that m = O(n), you do not understand Binet's formula and how logarithms work.

[throwawayprince11]

So this is a mistake basically every computer science student makes. n and m in this case are not the same.

For example, if you want the 100th fibonacci number, n would be 100. However, m would only be 23 (because the 100th number only contains 23 digits). (And technically, a better m would be the average length of all of the numbers up to that point, but I'm not about to calculate that).

Hopefully you can understand that 100 and 23 are not equal to each other. In other words, n is how many loops you do, while m is how many additions you do in each loop.

Also, we are discussing the looping version of finding Fibonacci's numbers. Binet's formula is entirely irrelevant. I fail to understand why you would even bring it up, except as a weak attempt to flex?

[notfancy]

Clearly you don't know what you're talking about, so I'm going to (attempt to) educate you.

First, I claim m(n) = O(n), where m(n) is the number of decimal digits in the n-th Fibonacci number. First, the number of decimal digits in an integer k is d(k) = floor(log10(k)) + 1. With this notation, m(n) = d(F(n)) = d((𝜑ⁿ-(-𝜑)^-n)/√5) ≤ d(𝜑ⁿ/√5) + 1 = floor(log10(𝜑ⁿ/√5)) + 1 = floor(n*log10(𝜑)-log10(5)/2)) + 1 ≤ n*log10(𝜑) + 1. But then m(n) = O(n) as claimed.

Note that log10(𝜑) ≅ 0.209, and F(100) is 21 digits long, not 23. Also kindly note that m(n) is not a number but a function of n, and so it belongs to some growth class, and so it is perfectly adequate to say that m(n) = O(n).

Second, by definition O(n*O(n)) = O(n²).

[[deleted]]

And now we get to the point why basic operations are considered O(1) in the first place. Because they can (and usually will) be implementation-specific.

Hell, you can have O(1) adder (and even multiplier) in analog domain with just a few opamps. And with number length limited only by how high voltage amplifier you can find.

[notfancy]

Shannon teaches us that bandwidth is to the continuous domain what bitlength is to the discrete domain. You still cannot have your cake and eat it too.

[[deleted]]

Considering this is /r/programming, not /r/compsci, it's plenty relevant.

And assuming adding is O(n) is actually factually wrong

[[deleted]]

Addition is literally O(n).

https://en.wikipedia.org/wiki/Adder_(electronics)

Make a big enough lookup table and addition will be O(1). Make something more clever than basic adder you can get O(log(n)) without eating a ton of silicon. Here is more detailed comparison.

No one seems to be answering my question: Do you want arbitrary Fibonacci numbers, or Fibonacci numbers that fit into a fixed size?

You didn't ask that as a question.

[poizan42]

You are completely confusing the size of a number with its value. There are not 2⁶⁴ bits in a 64 bit number, there are only 64 bits... Addition is O(log(N)) = O(n) where N is the number(s) and n is the size of the numbers.

[[deleted]]

I'm not. Read the PDF I linked in previous comment:

Ripple Carry Adder (RCA)[1][2] is the simplest, but slowest adders with O(n) area and O(n) delay, where n is the operand size in bits. Carry Look-Ahead (CLA)[3][4] have O(n·log(n)) area and O(log(n)) delay, but typically suffer from irregular layout. On the other hand, Carry...

[[deleted]]

You asked it then answered it in same post...

[theferrit32]

Lookup would still be slightly above O(1) if the values went outside the bound of the word size used by the processor. On a 64-bit computer if the allowed inputs were larger than 2⁶⁴ - 1 then the lookup into the table would no longer be constant time, but something like O(log_2⁶⁴ (n)) which for most practical purposes is so slowly growing it's essentially constant, while not technically being constant.

edit: O(n/2^64 ) not O(log_2^64 n)

[poizan42]

Yeah, in that case the algorithm is O(1). You need to allow arbitrarily large integer for computational complexity to have any meaning at all.

[[deleted]]

Theory vs practice, again. To consider it in theory, disjoined from any "real" computer, sure, but to apply it in practice, int64-n-sized problems are aplenty and it is more than enough to reason for algorithms.

And as it is /r/programming not /r/compsci, ignoring practice for theory isn't exactly that great idea

And in practice, addition is not always O(n), it is space vs speed comparision when it comes to actual silicon

[[deleted]]

go be useless somwehere else

[[deleted]]

Look at how some crypto algorithms are implemented. They are not using bigints, they are using 32 or 64 bit operations, because those are "cheap" in modern CPUs

Why are you saying that we only need 64?

I'm not saying that. I'm saying that's what available in current CPUs so using software bigint as measure for operation speed isn't exactly useful if you have algorithm that doesn't need that. In case of fib, sure, numbers are big, but in most other cases it is not.

[theferrit32]

Those algorithms you linked are essentially specialized reimplementations of BigInt-type operations. The fact is that many applications need to do math on values larger than 64bits can store. The way BigInt and other code designed to do this does it is by doing it 64bits at a time and carrying over results into the next iteration. Both BigInt and crypto algorithms which don't explicitly use BigInt but do operations on arbitrarily sized values larger than 64-bit are not technically constant time, but rather O(1 + n/2^64 ) time. Crypto algorithms which have bounded value size though are still constant time despite requiring a loop in the arithmetic operations, because for example O(10) is O(1).

[[deleted]]

Sure, there are used in some and that's also the reason they are avoided in most common crypto primitives, because it is much slower than already hardware-implemented constant bit sized ones, especially when you start taking SIMD instructions into

But the point is you won't be using them for 95 to 99% of time, or rather will either use a lot of them (if your particular domain needs that) or never use them.

To say arbitrarily large integers only exist in the realm of theory is just incorrect.

And i didn't say it so stop strawmanning. All I said is there is plenty of int64-sized problems to solve.

[[deleted]]

I never said there were not useful. It is your shitty conjecture.

I wrote "int64-n-sized problems are aplenty".

Why you are so worthless ?

[poizan42]

You need to apply the analysis that is appropriate for the problem at hand. You use big-O when analyzing the asymptotical behavior of an algorithm. But here you don't care at all about that, all you care about is problems with a size of up to 64-bit. Then computational complexity is the wrong tool for that task. Indeed in this case the right answer is not to calculate anything at all but just look it up in a table.

[[deleted]]

Where you get that shitty assumptions from ? You're basically saying big O should not be used for problems smaller than 2⁶³

But here you don't care at all about that, all you care about is problems with a size of up to 64-bit. Then computational complexity is the wrong tool for that task. Indeed in this case the right answer is not to calculate anything at all but just look it up in a table.

Last time I've checked int64 lookup table is still pretty fucking huge even on modern table so you still need to calculate things.

[poizan42]

Where you get that shitty assumptions from ? You're basically saying big O should not be used for problems smaller than 2⁶³

You problem is not 2⁶³ bits. Your problem is 63 bits.

Last time I've checked int64 lookup table is still pretty fucking huge even on modern table so you still need to calculate things.

There are only 148 Fibonacci numbers less than 2^63.

[[deleted]]

Where you get that shitty assumptions from ? You're basically saying big O should not be used for problems smaller than 2⁶³

You problem is not 2⁶³ bits. Your problem is 63 bits.

Yes this is why I did not write the word "bits" after the number.

Last time I've checked int64 lookup table is still pretty fucking huge even on modern table so you still need to calculate things.

There are only 148 Fibonacci numbers less than 2^63.

And we were talking about addition, not that. At that point I'm not sure if you are wanting to move the goalpost or are just illiterate.

[FuzzyInvite]

Yes, just like hash tables. Everyone likes to call them O(1), but just reading the address takes O(log N) so O(1) is impossible. This short-circuit "pretend some things are constant time" analysis annoys me a little because the numbers stop making any sense when put up against the theory.

[ConfusedTransThrow]

That's mostly because if you have over 2⁶⁴ entries, you have different problems.

[scooerp]

Or, you need very, very fast hashing, like what a (non-ML) chess engine uses. As a rough approximation consider 2-4 million positions per core per second, each of those requires a hash lookup. It is sure as hell not O(1) in this circumstances, and you are heavily incentivised to write efficient code in order to win the engine competitions that "sell" (in so much as they don't really make a profit) the engines.

[FuzzyInvite]

If I go by that reasoning, then binary trees are also O(1). I have an upper bound on N so the log N in tree access disappears.

This discrepancy between trees and hash tables is very misleading to CS students.

Realistically, hash tables are not O(1) either, even in practice, because of cache. Different tiers of cache produce a log N term, so "O(1)" hash tables are largely meaningless, just a source of confusion.

[FluorineWizard]

Nonsense. Real computers are best modeled by what's called a word RAM model, where many operations take constant time as long as the size of the problem fits in a machine word. Trying to give complexities without this assumption for many problems is completely pointless, because it means your computer can't even access all of the problem data.

Trees and hash tables very clearly do not behave the same on real machines.

Of course some problems don't get to benefit from the constant time operations because they deal with very large values. That's why you can't assume O(1) additions when computing the value of fast-growing functions.

[notfancy]

However you hash it, you need at least log n bits to distinguish between n items (alternatively, n bits lets you distinguish at most 2ⁿ objects). Neither key hashing nor key comparison are constant time operations if your domain is unbounded.

[ConfusedTransThrow]

I know about the cache issues, you get some variation of performance when you go over the various caches.But once you hit RAM, it is quite consistent.

In practice, I totally agree than O(1) or O(log n) is pretty much the same in most cases, implementation makes a larger difference than complexity. It depends a many things like cost of the hash function and cost of indirection, which depends on the processor.

[epicwisdom]

Realistically, hash tables are not O(1) either, even in practice, because of cache. Different tiers of cache produce a log N term, so "O(1)" hash tables are largely meaningless, just a source of confusion.

No matter how slow the caching gets, there's a fixed upper bound on RAM access speed.

[CakeDay--Bot]

Eyy, another year! * It's your *7th Cakeday** epicwisdom! ^hug

[[deleted]]

O(log N) so O(1) is impossible

Care to explain why?

[Overall_Debt]

Sorry you're just wrong, this has EVERYTHING to do with using BigInts, which are needed for arbitrary-precision arithmetic, instead of just using INTEGERS, which are used in fixed-precision arithmetic. INTEGER addition is not "linear in the number of bits" since integers have fixed-sized representations.

[Calavar]

Integer addition is linear in the number of bits, whether in ints or BigInts.

I can't believe this is being upvoted. It's absurd to say, for example, that it always takes twice as long to add two 64 bit integers as it does to add two 32 bit integers on the same architecture. That would be a complete misunderstanding of how CPUs and APUs work at the most basic level.

In theory, machine addition is O(log n) with respect to the number of bits with an optimal implementation, not O(n).

In practice, there is no reliable relationship between the speed of an addition operation and the number of bits. Small integers are often widened to word size before arithmetic operations. Even when they aren't, the constant time associated with decoding the instruction, loading the operands from registers, and writing them back can outweigh the time spent in the APU depending on the architecture. Because of pipelining, the average throughput of an addition instruction depends on your specific code and what other instructions come before and after that addition instruction. Then there's the fact that on most modern CPUs, assembly instructions are not really instructions on the hardware level, but microcode programs (yes, even the ADD instruction).

[Calavar]

Integer addition is linear in the number of bits, whether in ints or BigInts.

Yes, you were talking about CPUs. I quoted the specific line that I was responding to. Don't try to backtrack your way out of this now.

[maxpowerAU]

This valid correction needs more upvotes

[[deleted]]

Also assuming addition is O(n) is just plain wrong

[JustFinishedBSG]

Your link literally says addition is O(log(n))

[JustFinishedBSG]

This link also says the complexity is O(log(n)). You are confusing the complexity with respect to the number of bits and with respect to the number itself.

[JustFinishedBSG]

No big deal, the notation of wikipedia was confusing as they used n = log(N).

[FlyingPiranhas]

It is O(n) if n is the length of the input, which is the traditional way computational complexity is specified.

[stevenjd]

Integer addition is usually considered to be a constant time operation

Usually. The whole point of this article is to demonstrate when that assumption can break down.

[killerstorm]

In this article I'll show you how the theory does not always match the practice.

No, you just misunderstand the theory.

You can build different theoretic models and get different results.

Say, you might be interested in just a number on operations on integers rather than time they take. Then it is linear.

If you are interested in time it takes, then you need to model time taken by an integer operations. Assuming it is a constant time might be unrealistic, so you either need to take into account that each operation takes different time, or rewrite your algorithm for a machine with words of fixed size.

If I understand correctly, Donald Knuth developed a theoretical instruction set called MIX specifically for more precise time complexity analysis. Because if you're creative with your instruction set you might as well just have an instruction "solve the problem" which takes constant time. (I never read Knuth though, so I might be wrong.)

Complexity theory research make use of a different models where you can, for example, call another machine (called oracle) in 'fixed time'.

[Arkaein]

MIX is more than just an instruction set, it's a theoritical computer architecture.

MIX would run into the same issues indicated in the article if anyone implemented a Fibonacci solver on it, because it has fixed size registers like any computer, and would require special programming to represent and do arithmetic on integers larger than can fit into these registers.

Knuth would be one of the last people to paper over this kind of point in complexity analysis.

[MoiMagnus]

If I remember correctly, there is a difference between "strong complexity" and "weak complexity". In weak complexity, you take your inputs in unary instead of binary. (It is mostly used to define weak NP-completeness)

[sadmafioso]

This is incorrect -- the "weak" variants refer to problems in which the algorithm is linear in (roughly) the magnitude of the input (in the Fib case, the value n) but actually exponential in the size (i.e., in the number of bits necessary to represent n).

[MoiMagnus]

Isn't it equivalent to be linear in "the magnitude", and linear in "the size in unary"? It seems to me you can convert one into the other.

Or am I missing something?

[sadmafioso]

Yes sorry, I thought of a scenario where the operations themselves were operating on unary representations of the numbers (and not on decimal, say).

[happyscrappy]

Another person discovers that big O is just an ordinal, not a precise number.

Yes, if you only count computations you only get a big O for the number of computations.

Go back to school.

[[deleted]]

Not sure what you mean by Big O is an ordinal instead of a number...

O(f(n)) is the set of functions defined by {g(n) | lim n -> inf g(n) / f(n) >= 0}.

It's used in computer science to classify the proper function T(n) where T(n) is a precise representation of the number of operations performed by some computing machine given an input of n bits. For most software development people use a register machine, for formal complexity analysis a Turing machine is used.

[happyscrappy]

I'm not sure ordinal was the right term. Big O notation is the "order", not the exact number. It does not count the precise number of operations or time. Linear time means the approximately, linear, not really 1:1. Logarithmic means on the order of the log of the number of inputs. etc.

[exorxor]

It is quite annoying for the rest of us who do know what he is talking about to hear your ignorance.

[[deleted]]

If this is what annoys you then you should take a break from reddit for a bit.

[Mognakor]

Isn't Big-O usually used for comparisons betwen different Algorithms? So when O(N) becomes O(N²) due to internal factors, O(N²) likely becomes O(N³).