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

#1 umuber  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 12-December 13

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

Posted 16 February 2017 - 05:05 PM

Computational complexity is usually described in terms of the size of the input data sets. Is there a formalism that describes complexity when the size of the data set is irrelevant? For example, say I have an algorithm and the number of operations depends only on the value of the variable x. Let's say the number of operations is N = a*x^3 + b*x^2 + c*x^1. Would the complexity be written as O(x^3), or is there another notation for this? Is there a notation that describes linear changes in complexity?

Is This A Good Question/Topic? 0
  • +

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

#2 Motoma  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 452
  • View blog
  • Posts: 798
  • Joined: 08-June 10

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

Posted 16 February 2017 - 06:16 PM

View Postumuber, on 16 February 2017 - 07:05 PM, said:

Computational complexity is usually described in terms of the size of the input data sets.


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.

View Postumuber, on 16 February 2017 - 07:05 PM, said:

For example, say I have an algorithm and the number of operations depends only on the value of the variable x. Let's say the number of operations is N = a*x^3 + b*x^2 + c*x^1. Would the complexity be written as O(x^3).


Close. This would still be represented as O(n^3).
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2499
  • View blog
  • Posts: 3,952
  • Joined: 21-June 11

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

Posted 16 February 2017 - 06:28 PM

View Postumuber, on 17 February 2017 - 01:05 AM, said:

Computational complexity is usually described in terms of the size of the input data sets.


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

Would the complexity be written as O(x^3)


Yes.

View PostMotoma, on 17 February 2017 - 02:16 AM, said:

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


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.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

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

Posted 17 February 2017 - 06:36 PM

Slightly off topic.

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.

Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

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

Posted 20 February 2017 - 12:54 PM

Quote

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.


I believe Hash Table operations are amortized O(1).

Quote

Yes, I know I'm sounding a lot like that CS teacher who has been asserting that hashtables are not O(1).


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.
Was This Post Helpful? 1
  • +
  • -

#6 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

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

Posted 23 February 2017 - 08:00 AM

So checking if a number is prime or not can be done as amortized O(1). :) Simply do the following:
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. :)
Was This Post Helpful? 0
  • +
  • -

#7 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

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

Posted 23 February 2017 - 01:41 PM

There's a couple problems with that. I think you need to be a little more rigorous than "occasionally" for amortization analysis. You have to be able to show that the amount of "sieving" that is done is proportional to the number of candidates that are presented to this function. For example, if we look at amortization of array resizing, we double the size when we run out of space from inserting and halve the size when the number of elements falls below one quarter the capacity when deleting. This ensures the number of "copy operations" done to the elements is no more than the number of inserts and deletes. Since an individual copy operation is constant that means per insert or delete all of the array resizes are amortized constant. Your algorithm on the other hand randomly resizes and sieves. So, we can easily find a sequence of inputs that sieves on every input. Also, even if your analysis were correct, you would not be comparing apples to apples for primality testers. Primality testers usually only have the candidate as their input. Your input is the candidate and the pre-sieve array. Thus, you would have an O(1) solution for an unlimited input. Your algorithm is basically provided with both the answer and the question which at the very least makes it less interesting.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 5823
  • View blog
  • Posts: 19,821
  • Joined: 05-May 12

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

Posted 26 February 2017 - 10:39 AM

View Postmojo666, on 23 February 2017 - 03:41 PM, said:

I think you need to be a little more rigorous than "occasionally" for amortization analysis. You have to be able to show that the amount of "sieving" that is done is proportional to the number of candidates that are presented to this function.


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.
Was This Post Helpful? 0
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

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

Posted 25 March 2017 - 11:18 AM

Sorry I'm so late to this but I want to give a reason why big-oh is inevitably tied to size of the input in almost all cases. It's not that all algorithms scale with size but it is the case that if you went by size you could make safe bets about the running time of almost all algorithms.

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

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1