calculate big oh notation with for loop condition

Question

I am trying to understand the calculation of Big-oh notation of a function, when a function contains a for-loop, which has a specific condition

for (initialization, condition, increment)

or() like below:

    public void functE( int n ) 
    {
       int a;
       for ( int i = 0; i < n; i++ )
           for ( int j = 0; j <= n - i; j++ )
               a = i;
    }

I suppose the big-oh of this function to be O(n^2), is this valid?

Given that the code is side-effect free and returns `void`, the runtime should be `O(0)`. — EOF, Sep 10 '19 at 20:05
@EOF: I think the assumption is you *aren't* using an optimizing compiler. — Scott Hunter, Sep 10 '19 at 20:08
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Sep 10 '19 at 22:13

score 1 · Accepted Answer · answered Sep 10 '19 at 20:16

1

Assuming a = i takes 1 time unit, you can consider each i:

i = 0 : n + 1
i = 1 : n
i = 2 : n - 1
...
i = n - 1 : 2

So in total:

T(n) = (n+1) + (n) + (n-1) + ... + 2 = n + [1 + ... + n] = n + n * (n + 1)/2 = (n^2 + 3n) / 2 = O(n^2)

answered Sep 10 '19 at 20:16

Hadi GhahremanNezhad

2,377
5
29
58

score 0 · Answer 2 · answered Oct 22 '21 at 17:35

0

by using tabular method ,complexity is n^2+(2-i)n+2

a cording to the Big-Oh notation,

let f(n)=n^2+(2-i)n+2
f(n) <= c*g(n)
n^2+(2-i)n+2 <= n^2+(2-i)n+(2-i)n
n^2+(2-i)n+2 <= n^2+2(2-i)n
n^2+(2-i)n+2 <= n^2+n^2
n^2+(2-i)n+2 <= 2n^2

therefore, c=2 and g(n)=n^2, f(n)=O(g(n)) = O(n^2)

answered Oct 22 '21 at 17:35

Meghana Chippada

1

As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Oct 22 '21 at 18:11
You seem to know what you're doing, but I'm afraid I can't follow you. Would you mind to elaborate? More to the point: I'm familiar with the Landau O, but I don't know the tabular method. Can you provide us a link? And I don't see the connection between your formulas and the source code of the question. I'd appreciate explanations of each line. Thanks in advance! – Stephan Rauh Oct 22 '21 at 19:04

calculate big oh notation with for loop condition

2 Answers2