Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Felix Ungman

Member Since 19 Nov 2007
Offline Last Active Today, 01:23 AM

Posts I've Made

In Topic: Is Google Play Game Services or Apple Game Center worth it?

Yesterday, 01:05 AM

@Oluseyi Good pst! If this was Stack Overflow it had to be marked as the officially *accepted* answer.

 

You know how Apple now allows anyone to download beta versions of iOS and install on their phones? You may not believe it, but people have given us 1-star reviews for not working as expected on a beta version that was released just that afternoon!

 

A minor clarification/update: iOS testflight betas are invitation only, and I also believe Apple recently removed the ability to rate/review beta versions.


In Topic: Is O(0) equal to O(1) ?

13 July 2015 - 08:31 AM

 

 


O(0) would mean a complexity that tends toward zero for large input sizes. It may still take a ridiculously large amount of clock time, but you know that if you provide larger numbers tending out to infinity, asymptotically the complexity is continually decreasing. The function -- whatever it is -- becomes progressively less complex to solve the bigger the input, asymptotically reaching no complexity at all.

 

Not sure I agree with this at all.. that would be O(1). O(0) is only the empty algorithm. NOP is not O(0), an empty function that is actually a function is not O(0), ret 0 is not O(0), the only thing that is O(0) is nothing, the empty algorithm that is never started and never ends as it is nothing. Try to call it on the complete set of particles in the universe and it is never run, the algorithm is never started and never existed as it was erased on compile-time.

If one source contains an algorithm and another does not and they yield identical bytecode after compilation, then that algorithm is O(0).

 

Leaf-methods on trees where only branches have code can reasonably be described as O(0), if they are expected to be optimized out for example. Can't think of an example where it would make a difference for the final O(..) .. but I somehow suspect there might be some example where a sub-algorithm that is expected to removed would give a theoretical answer closer to reality if it was designated O(0) rather than O(1) in the analysis.

 

 

I'm going to disagree slightly with both of these. To me the most coherent definition of O(0), at least based on the definition of O I've always used (which is the same as Wikipedia's) is to say that f(x) is O(0) if and only if f(x) is the empty algorithm for values of x larger than some (finite) x0.

 

Similar to what frob is saying, but I don't think saying that a function tends toward having no complexity is quite strong enough, as it permits that the function f(x) may still have non-zero complexity for all values of x.

 

 

Why a special definition of O(0)? It works well with the ordinary one:

 

 03f0892b09b6d78de9ced3fbedce20a2.png if and only if ebd6ac0cecd43f567e44f420d16cba4c.png

 

Set g(x) identical to zero and f(x) = 0 for all x >= x0. You could then either prove or define the empty algorithm to be precisely the algorithm that takes zero time. The empty algorithm doesn't depend on anything, and in particular it doesn't depend on x, so it would take no time regardless of input. No matter what angle you approach this the result should be the same.


In Topic: Is O(0) equal to O(1) ?

11 July 2015 - 12:00 PM

 

Without a rigorous computational model (what it means for an algorithm or a piece of code to "compute" or "take time") the whole discussion is moot and saying that something "has time complexity O(0)" is handwavy and/or meaningless, whereas we can rigorously say that a function (in the mathematical sense) is or is not in O(0).

 

 

Is it? If you are discussing time complexity in terms of O(...) how can O(0) be any more moot than O(1)? The math is as you say rigorously well defined, even if the computational model not always is. Elided code (e.g. inlined empty function body) can be meaningful from a higher perspective but should reasonably have time complexity O(0).


In Topic: Is O(0) equal to O(1) ?

11 July 2015 - 01:00 AM

On the other hand, if an O(0) function that depends on a variable x takes non-zero time for some x, it would need to do some computation involving x (at least for those values). That would be O(1) at best, and I cant see a way it could do that check only for those values smaller than some number N. So it seems, for functions that are O(0) they always take no time.


In Topic: Re-getting into C++ again

06 June 2015 - 02:00 PM

Pick a project (anything simple enough, such as tic-tac-toe or even math quiz) and do not worry so much about forgetting stuff (but make sure to use a good IDE and compiler). I forget stuff all the time, even though I program every day. When I do, my tools are there to remind me.


PARTNERS