1

If I have a function that takes n*g operations for input size n, but g << n, would I be able to say the function is linear wrt n?

voidobscura
  • 17
  • 2

1 Answers1

2

Not necessarily. For example, if g = log(n), it is true that g << n yet O(n * g) is not linear in n (it is O(n log(n))).

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • that is not true if g is constant, for example. the OP hadn't stated nothing about the nature of g. – linski Sep 12 '13 at 20:48
  • it's a user-chosen variable, but in practical cases g would be a constant the user decides which would be much smaller than n. – voidobscura Sep 12 '13 at 20:59
  • then it is linear, as you said. see [here](http://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant). – linski Sep 12 '13 at 21:04
  • thanks - i didn't know how to determine the complexity because g is meant to be a constant much smaller than n, but for example, the user could specify a value of g = n as well. however, the nature of the function specifies that g be << n – voidobscura Sep 12 '13 at 21:09
  • read [this](http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds) answer and [this](http://stackoverflow.com/questions/10923764/time-complexity-of-a-program-which-involves-multiple-variables) answer. – linski Sep 12 '13 at 21:25