Member Avatar for Rick1980

Hi all,

I'm trying to figure out the runtime complexity of an algorithm I
created. I narrowed the basic problem down to two nested sums.
However I need the Big O notation of this problem. I converted the
formula into the following nested loops. I have the feeling that
this problem is still squared. Can you please help me deriving the
Big O notation?

For(int j = 0; j =< N; j++){
For(int i = 1; i =< N-j; i++){
2*A*i;
}
}

A here is A constant factor.

many thanks

Rick

  • 2 Contributors
  • 2 Replies
  • 82 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by Rick1980
Member Avatar for Narue

Unless you care about working out the math for the diminishing size of the inner loop (in which case you shouldn't have any problem with it), the complexity is quadratic because that's the upper bound.

Member Avatar for Rick1980

Thanks that was a great help :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.