BigO Counting Creation of Arrays?

Do you count this to find num of steps?

Page 1 of 1

3 Replies - 1215 Views - Last Post: 05 October 2007 - 05:08 AM Rate Topic: -----

#1 UnderTheBridge   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-October 07

BigO Counting Creation of Arrays?

Posted 04 October 2007 - 08:07 PM

I am learning about how to count BigO steps and I have it mostly down accept for one question. Do you count the creation of an array as a step? I am pretty sure that just creating a variable isn't counted so I would think the answer is no? Just looking to make sure, thanks.

Examples:
//Pretty sure just creating variables isn't counted as in this case
int i1;

//But would it be counted if it was for an array?
int iArray[] = new int[n];


Is This A Good Question/Topic? 0
  • +

Replies To: BigO Counting Creation of Arrays?

#2 spullen   User is offline

  • D.I.C Regular
  • member icon

Reputation: 10
  • View blog
  • Posts: 356
  • Joined: 22-March 07

Re: BigO Counting Creation of Arrays?

Posted 04 October 2007 - 09:50 PM

I think it's just O(1)
Was This Post Helpful? 0
  • +
  • -

#3 UnderTheBridge   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-October 07

Re: BigO Counting Creation of Arrays?

Posted 04 October 2007 - 11:02 PM

That makes sense to me! Thanks, do you by chance know what O() a recursive method would be? Or does that depend on the situations in which it calls itself?

**Edit**
I think I found it. O(n) is what I think it is since there is no loops but only recursive calls.

This post has been edited by UnderTheBridge: 04 October 2007 - 11:19 PM

Was This Post Helpful? 0
  • +
  • -

#4 spullen   User is offline

  • D.I.C Regular
  • member icon

Reputation: 10
  • View blog
  • Posts: 356
  • Joined: 22-March 07

Re: BigO Counting Creation of Arrays?

Posted 05 October 2007 - 05:08 AM

No O(n) wouldn't be right for a recursive function because if you think about it you are doing iteration like a for or while loop. And there are a ton of different recursive methods and they all can have different runtimes. For instance mergesort can be a recursive function, and this has a big O of O(nlogn). And then there are different types of recursion for instance a simple factorial method could go all the way until the end push everything onto the stack and then do the arithmetic when popping off the stack (I think this form of recursion is called tree recursion but I can't remember), or you could do it with tail recursion where it just pushes the method call on the stack with the result being calculated each time and being passed in as a parameter and then once it hits the base case it just returns that result and you don't have to pop anything off the stack.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1