Big-O Question

[Matt8541]

Hello,

 

First post here. Question is in regards to Big-O. I'm wondering if a method calls another method which is O(n), does this method become O(n) as well. If not, why not? It seems that it should be.

 

Here's an example (and my professor marked this as O(1), but it calls an O(n))

 

 

public void push (T element)

{

if (size() == stack.length)

expandCapacity();

 

stack[top] = element;

top++;

}

 

private void expandCapacity()

{

T[] larger = (T[])(new Object[stack.length*2]);

 

for (int index=0; index < stack.length; index++)

larger[index] = stack[index];

 

stack = larger;

}

 

So why is the push function not O(n)?

[Schrödinger's hat]

Hello,

 

First post here. Question is in regards to Big-O. I'm wondering if a method calls another method which is O(n), does this method become O(n) as well. If not, why not? It seems that it should be.

 

Here's an example (and my professor marked this as O(1), but it calls an O(n))

 

 

public void push (T element)

{

if (size() == stack.length)

expandCapacity();

 

stack[top] = element;

top++;

}

 

private void expandCapacity()

{

T[] larger = (T[])(new Object[stack.length*2]);

 

for (int index=0; index < stack.length; index++)

larger[index] = stack[index];

 

stack = larger;

}

 

So why is the push function not O(n)?

 

 

expandCapacity() is O(n), but it doubles the capacity of the stack when called.

size() == stack.length

will only return true on average 1/n times.

[khaled]

public void push (T element)
{
      if (size() == stack.length) 
             expandCapacity();

      stack[top] = element;
      top++;
}

private void expandCapacity()
{
      T[] larger = (T[])(new Object[stack.length*2]);

      for (int index=0; index < stack.length; index++)
             larger[index] = stack[index];

      stack = larger;
}

 

the function top complexity is not O(1), it's O(g(x)) .. where g(x) = complexity of expandCapacity = O(n)