-3

Forgive me if this has been answered, as my phone isn't letting me search StackOverflow. I searched Google but couldn't find any information.

I'm an aspiring programmer learning C++. While I'm reading people's questions and such, I see the term "O(n)" releatively often.

Could anyone shed some light on this and tell me what that means?

cadaniluk
  • 15,027
  • 2
  • 39
  • 67
Puma SPNKr
  • 11
  • 2
  • 2
    https://en.wikipedia.org/wiki/Computational_complexity_theory – Neil Kirk Oct 21 '15 at 21:02
  • that the execution time increases linearly with the size of data you're going over. so if you have double the number of elements to process, the algorithm will take twice the time. – Adam D. Ruppe Oct 21 '15 at 21:02
  • 2
    it actually is. search up Big O notation on google, its a way of measuring algorithmic complexity. – R Nar Oct 21 '15 at 21:03
  • @Baum MIT Augen - I'm sorry, I thought it was. I literally have no idea what it means but it comes up when I research programming C++. Sorry for the confusion and thank you everyone who has answered!! – Puma SPNKr Oct 21 '15 at 21:03
  • Formally speaking, a function f(N) is O(N) if there is some point along the domain of N beyond which f(N) is always less kN, for some constant k. More conversationally, it means that as N becomes large, you can consider the *maximum* growth rate of f(N) to be that of some linear function (as opposed to a quadratic function, or a cubic function, or a quadratic function, or...). Typically, in programming contexts, N is the size of some input to a program or algorithm, and f(N) is a function describing the quantity of some resource being consumed by that algorithm, such as time or memory. – Asad Saeeduddin Oct 21 '15 at 21:13

1 Answers1

3

It means "ordo n", that is, a difficulty on the order of n.

O(n) means, in a cycle of n iterations, for every n there is only a single algorithmical step to be taken, that being, the algorithm is actually linear.

O(n log n) means the difficulty of algorithm is n times log n, that is, getting logarithmically harder as n grows.

As an excuse, it is true that this is not a programming question, but it is often encountered on job interviews and similar.

Victor - Reinstate Monica
  • 1,264
  • 9
  • 11
  • 2
    I just want to thank you for taking time to answer this for me. Someone posted a link redirecting to where the question was answered already, but if they did not, you would have gotten the credit. Thank you again. – Puma SPNKr Oct 21 '15 at 21:11