Big-O Algorithm Efficiency

Express the tightest upper bound of the following loops in big-O notat

Page 1 of 1

4 Replies - 5891 Views - Last Post: 10 February 2007 - 08:55 AM

#1 EquinoX  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 63
  • Joined: 19-January 07

Big-O Algorithm Efficiency

Posted 19 January 2007 - 05:27 PM

e) for (int j = 0; j < n; j++)
sum += j;


a) int sum = 0;
int n = 100000;


f) for (int j = 1; j < n; j *= 2)
sum += j;
Is This A Good Question/Topic? 0
  • +

Replies To: Big-O Algorithm Efficiency

#2 Nova Dragoon  Icon User is offline

  • The Innocent Shall Suffer, Big Time
  • member icon

Reputation: 36
  • View blog
  • Posts: 6,169
  • Joined: 16-August 01

Re: Big-O Algorithm Efficiency

Posted 19 January 2007 - 05:30 PM

We are not here to do your homework for you,

Ask a clear question, and post relevant code that you have
Was This Post Helpful? 0
  • +
  • -

#3 EquinoX  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 63
  • Joined: 19-January 07

Re: Big-O Algorithm Efficiency

Posted 19 January 2007 - 05:41 PM

Express the tightest upper bound of the following loops in big-O notation. This is the question. I just learned about big-O and still don't really get about it. Can someone just give me an answer of the question that I asked with an explanation of it so I can understand more about this
Was This Post Helpful? 0
  • +
  • -

#4 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Re: Big-O Algorithm Efficiency

Posted 10 February 2007 - 08:28 AM

Big O is reletivly easy to understand heres an overview.

consider the function 3x^4 + 2x^3 + x^2 + 3

we would say that this function is Big-O of x^4
when the constant is 9.

a function is Big O when F(x) <= Cg(x) where C is some constant and g(x) is a function that is always bigger than F(x)

Generally when you do Big O you raise all coefficients to the same power (ie x^4 in this case) and then simplify.

for programming purposes any statement that takes one line (ie assignment, printing) is said to be BigO(1) because it takes a negligible amount of time. functions like for loops USUALLY take n times so its said to be BigO(n). if you have an if loop then calculate the Big O for the true statement and the false statement and take the maximum value. If you ahve nested for loops then generally it is said that they are BigO(n^2)

hope this helps some.
Was This Post Helpful? 0
  • +
  • -

#5 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Big-O Algorithm Efficiency

Posted 10 February 2007 - 08:55 AM

nice explanation mattman059.

there have been many threads on big-O, most including code which looks almost exactly like the one's you have posted. Big-O is not a complicated notation, it simply tries to determine a "worst case runtime" for the code. A for loop has a worst case if every element is searched, now determine the number of elements that could be searched and there is your answer.

*Coeffecients are always dropped, eg:
1) n/2 = 1/2 * n = n -> O(n), linean time
2) 2n = 2 * n = n -> O(n), still linear
3) 5 = 5 * 1 = 1 -> O(1), constant time

it is interesting to note that even though an algorithm in n/2 and 2n appear to have large differences in runtime, yet, in practise on large data sets will run in approximately linear time as an upper bound :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1