CODEWITHSUNDEEP
performancealgorithm
Shani
Shani

Reputation: 447

Computational complexity in Big-O notation

How can I specify computational complexity of an algorithm in Big-O notation whose execution follows the following pattern, according to input sizes? 

Input size: 4
Number of execution steps: 4 + 3 + 2 + 1 = 10

Input size: 5
Number of execution steps: 5 + 4 + 3 + 2 + 1 = 15

Input size: 6
Number of execution steps: 6 + 5 + 4 + 3 + 2 + 1 = 21

Upvotes: 0

Views: 208

Answers (3)

akanksha1105
akanksha1105

Reputation: 348

For any series which follows the pattern 1 + 2 + 3 + 4 + ....+n , the sum of the series is given as n(n+1)/2, which is O(n^2)..

In your case , the number of steps will never be n^2, because at each level we are doing one step less(n + n-1 + n-2),however the big Oh notation is used to specify the upper bound on the growth rate of a function thus your big O will be O(n^2) because it is more than n number of steps but less than n^2 number of steps.

Upvotes: 3

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

Technically, you have not given enough information to determine the complexity. On the information so far, it could take 21 steps for all input sizes greater than 5. In that case, it would be O(1) regardless of the behavior for sizes 4 and 5. Complexity is about limiting behavior for large input sizes, not about how something behaves for three extremely small sizes.

If the number of steps for size n is, in general, the sum of the numbers from 1 through n then the formula for the number of steps is indeed n(n+1)/2 and it is O(n^2).

Upvotes: 4

bhuang3
bhuang3

Reputation: 3633

I think it should be O(N), because it's just like : Given an array with N size, and iterate it (if we don't care the plus computation time).

By the way, I think the (n + 1)*n/2 is just the result of sum, not the algorithm complexity.

Upvotes: -2

Related Questions