## 8 Replies - 1060 Views - Last Post: 25 March 2017 - 11:18 AM

### #1

# Complexity as a function of a real number. Big-O notation?

Posted 16 February 2017 - 05:05 PM

##
**Replies To:** Complexity as a function of a real number. Big-O notation?

### #2

## Re: Complexity as a function of a real number. Big-O notation?

Posted 16 February 2017 - 06:16 PM

umuber, on 16 February 2017 - 07:05 PM, said:

Not exactly. Big O notation describes the computational complexity as it relates to the adjustment of some input. One of the canonical ways of adjusting the input is by increasing the input's size. However, that doesn't mean that your computational complexity couldn't be related to the value of a single input, rather than the number of inputs. A simple example would be a program that determined if a number was even by subtracting two repeatedly:

def isEven(num): while while n > 1: n = n - 2 return n == 0

This simple function is solely dependent on the input's value, and is roughly linear. That is to say this is an O(n) algorithm.

umuber, on 16 February 2017 - 07:05 PM, said:

Close. This would still be represented as O(n^3).

### #3

## Re: Complexity as a function of a real number. Big-O notation?

Posted 16 February 2017 - 06:28 PM

umuber, on 17 February 2017 - 01:05 AM, said:

Usually, yes, but not always. For example the complexity of graph algorithms is often expressed in terms of the number of nodes and the number of edges, for example the worst-case runtime of Dijkstra's algorithm is O(|E| + |V| log |V|) where |V| is the number of nodes and |E| is the number of edges.

It is also not uncommon to express the complexity in terms of the input value as you want to do.

Keep in mind though that complexity classes

*are*defined in terms of input size, not input values. So if you show that your algorithm is in O(x^3) where x is the value of the input, you have

*not*shown that it is in P because P requires it to be in O(n^c) where n is the input

*size*.

Quote

Yes.

Motoma, on 17 February 2017 - 02:16 AM, said:

Why? I'd definitely prefer O(x^3) here. Since the variable is called "x" in the code and "x" has no conventional other meaning, it is clear to the reader that x refers to the argument's value. If you write O(n^3) the reader will assume that n refers to the input size because there is n in the code and n usually refers to the input size.

My guideline for these things would be: without explanations you can use n to refer to the input size, |V| and |E| to refer to the number of nodes and edges in a graph respectively and the name of a variable from the code to refer to the value of that variable.

In all other cases you should specifically mention what each variable refers to. For example "O(n + m) where n refers to the size of array1 and m to the size of array2" is okay, but if you cut the explanation, it's entirely unclear.

### #4

## Re: Complexity as a function of a real number. Big-O notation?

Posted 17 February 2017 - 06:36 PM

What? Wait. If big O is dependent on input size then a hash table would be not O(1) for inserts and/or lookups. At some point I will run into collisions and I will have to do work to resolve the collision either by probing, chaining, resizing the hashtable, or some other technique that will one way or another dependent on the number of items that I already have in the hash table. Even if I used chaining by insert to the front of a linked list, an O(1) operation, the lookup for the item would be O(N).

Yes, I know I'm sounding a lot like that CS teacher who has been asserting that hashtables are not O(1). A lot of folks (and I have to admit that I belong to that group) have dismissed him as crazy. But now his arguments are starting to sound more plausible. Wish I could find the links to his blog again so that I can re-read with a new perspective. Granted when I first ran across his blog, he was actually talking about the cost of computing the hash as not being O(1), and not necessarily the data structure manipulation.

Which brings this back on topic... He was arguing that the hash computation depended on the key value.

For the curious, I found his blog post again: Do hash tables work in constant time?

And I stumbled across this in Reddit which has the same questions I had about number of inputs, collisions, and resizing: Why is hashtable lookup O(1) rather than O(log n) or O(n)

This post has been edited by **Skydiver**: 17 February 2017 - 09:13 PM

Reason for edit:: Added link to the blog post I was alluding to.

### #5

## Re: Complexity as a function of a real number. Big-O notation?

Posted 20 February 2017 - 12:54 PM

Quote

I believe Hash Table operations are

**amortized**O(1).

Quote

I think the confusion here is that we are looking at the complexity of hash operations with respect to the number of records in the hash table. The operations don't really perform any differently (amortized) if there is 1 or 1 billion records. Thus with respect to the number of records, the performance is O(1). We are only concerned with the number of records because Hash Tables are designed to compete with other collection data structures such as arrays and linked lists that experience inefficiencies in operations as the collection grows.

The professor's argument is that as the number of records grows, then the key will necessarily have to grow with it thus changing the performance of the hash function. I think objectively he is correct, but this metric is irrelevant to what we are trying to measure. Other data structures have the exact same problem (in some cases a worse problem) with the size of the key so the hash table is going to be no worse than the other data structures with that respect.

### #6

## Re: Complexity as a function of a real number. Big-O notation?

Posted 23 February 2017 - 08:00 AM

Let sieve[] = { false, false, true, true, false, true, false, true } max = count of sieve -1. If candidate is greater than max new_sieve = array[0..candidate] copy old sieve into new sieve let sieve = new_sieve continue sieving from max to candidate return sieve[candidate]

The sieving will only happen occasionally as compared to the random candidates that come in.

### #7

## Re: Complexity as a function of a real number. Big-O notation?

Posted 23 February 2017 - 01:41 PM

### #8

## Re: Complexity as a function of a real number. Big-O notation?

Posted 26 February 2017 - 10:39 AM

mojo666, on 23 February 2017 - 03:41 PM, said:

I agree. I should have expanded on that more. I was assuming that the candidate numbers coming in would be randomly distributed. In the back of my head, I had exactly the idea about the doubling the size of the array scenario. Instead of the array doubling in size for each input added, I was banking on the probability that the next random number that comes in would be less than the highest number seen so far.

And yes, I know I was not doing an apples to apple comparison between real primality testers and my proposed algorithm, the same way a the complexity analysis for cracking unsalted NT LanMan hashes would be when using rainbow tables vs. brute force.

### #9

## Re: Complexity as a function of a real number. Big-O notation?

Posted 25 March 2017 - 11:18 AM

Take the example where your code runs in time proportional to the number you input not the size of the number. We call this O(n) where N = 2^n. N is the size while 'n' is the value of the size. Well as it turns out O(lg(N)) denotes the same set of functions that O(n) does! Should this happen in general? Well no not formally but in a certain sense there's a good reason to suspect it in almost every case.

Say you come up with some crazy encoding of the natural numbers in binary. It's an encoding that ensures that size (number of bits) has nothing to do with the value of the input. Well unfortunately you're doomed because I can still find an increasing subset of numbers that increase with size and more over for any given size the value has a bound and this bound is non-decreasing with respect to size! Take all the numbers that are encoded with 2 bits. Choose the maximum of those numbers as my first number. Now take all the numbers encoded with 3 bits. Take the maximum of those to be my second number. Repeat this step. This is a non-decreasing sequence of numbers with non-decreasing size. Indeed the bounds that I mentioned are exactly these numbers. In fact I can pull this trick off for any orderable property you can think of on any data structure! So you're screwed in a certain sense. It won't always be so cut and dry as O(lg(N)) = O(n) but never the less a more expensive example will always lurk in a bigger example for any example you can give.

The insight I'm trying to give is something physicists try to give for entropy. Why should the world devolve into chaos? Because there are more ways for things to be chaotic than to be ordered. Why should the running times of algorithms depend on size? Because there are more ways for big things to be ill-behaved than there are for small things to be ill-behaved.

So there are good theoretical reasons to expect algorithms performance to depend on size.

Lastly I'd like to give an example of an algorithm that has running time that really doesn't seem to depend on size. In reality it still does in the above mentioned sense but the way in which it does it is the least direct that I know of. You can find this algorithm here: http://math.andrej.c...ional-programs/

I grant you this tutorial is really hard to follow but if you put the work into you realize that it is indeed very important to have many other notions of measures that we measure the performance of code with respect to. Most of the interesting ones however are at higher types so typical programmers don't run into them very often. Here's a secret however. The above thing I mentioned is still almost applicable. If you take your encoding of each sequence to be the smallest description of that sequence then this holds. However because an infinite number bigger descriptions exist for any sequence the connection is not so strong here.

Hopefully this lends some more insight into this.

This post has been edited by **ishkabible**: 25 March 2017 - 11:20 AM