4

I was working on the water-collection between towers problem, and trying to calculate the bigO of my solution for practice.

At one point, I build a 2D array of 'towers' from the user's input array of heights. This step uses a nested for loop, where the inner loop runs height many times.

Is my BigO for this step then n * maxHeight?

I've never seen any sort of BigO that used a variable like this, but then again I'm pretty new so that could be an issue of experience.

I don't feel like the height issue can be written off as a constant, because there's no reason that the height of the towers wouldn't exceed the nuber of towers on a regular basis. 

  //convert towerArray into 2D array representing towers
var multiTowerArray = [];
for (i = 0; i < towerArray.length; i++) {
  //towerArray is the user-input array of tower heights
    multiTowerArray.push([]);
    for (j = 0; j < towerArray[i]; j++) {
        multiTowerArray[i].push(1);
    }
}
Community
  • 1
  • 1
Bricky
  • 2,572
  • 14
  • 30

1 Answers1

2

For starters, it's totally reasonable - and not that uncommon - to give the big-O runtime of a piece of code both in terms of the number of elements in the input as well as the size of the elements in the input. For example, counting sort runs in time O(n + U), where n is the number of elements in the input array and U is the maximum value in the array. So yes, you absolutely could say that the runtime of your code is O(nU), where n is the number of elements and U is the maximum value anywhere in the array.

Another option would be to say that the runtime of your code is O(n + S), where S is the sum of all the elements in the array, since the aggregate number of times that the inner loop runs is equal to the sum of the array elements.

Generally speaking, you can express the runtime of an algorithm in terms of whatever quantities you'd like. Many graph algorithms have a runtime that depends on both number of nodes (often denoted n) and the number of edges (often denoted m), such as Dijkstra's algorithm, which can be made to run in time O(m + n log n) using a Fibonacci heap. Some algorithms have a runtime that depends on the size of the output (for example, the Aho-Corasick string matching algorithm runs in time O(m + n + z), where m and n are the lengths of the input strings and z is the number of matches). Some algorithms depend on a number of other parameters - as an example, the count-min sketch performs updates in time O(ε-1 log δ-1), where ε and δ are parameters specified when the algorithm starts.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thanks, glad to see my intuition wasn't totally off! In what cases would these not be included in the BigO notation? It seems like here it's necessary to include, but only because the height/sum could reach or surpass n. Is that correct? – Bricky Aug 26 '16 at 20:50
  • 1
    Most algorithms don't depend on the numeric values of their inputs, but (as in this case) some do work proportional to these values. That's the most common case where you see this come up. – templatetypedef Aug 26 '16 at 21:02