Re: Help with Big O notation

first, you need to wrap the code

[CODE]

......

[CODE]

so we can throughly read it and give you pointers, but the best things in general:

- all primitive statements: prints are all O(1)

- all loops are O(n)

- all nested loops are O(n * m *...*q); where n,n,...q could be any variable, if they are all the same iterations then O(n**k) where k is a power := number of loops

NOTE: assuming the loops go through the entire list

else:

O(k) where k is a positive integer, which is the number of iterations it goes through

just practice and check out videos online or check your discrete mathematics book for references. Good luck

Re: Help with Big O notation

Quote:

Originally Posted by

**mxcnrawker** - all loops are O(n)

A O(log(n)) loop:

Code:

`for (int i= 1; (i<<= 1) < n; ) ...`

A O(n*n) loop:

Code:

`for (int i= 1; i < n*n; i++ ) ...`

etc. etc.

kind regards,

Jos

Re: Help with Big O notation

Also, even something as trivial as a print can be something other than O(1) if the thing being printed is the result of a method which is not O(1). I assume you meant printing things like strings, but a blanket statement like Quote:

prints are all O(1)

is misleading.

OP, this looks like a homework dump. Figuring this stuff out is the assignment, and usually needs to be done by hand. You need to derive a basic formula for the number of times something happens in a code block and simplify that to big oh notation.

mxcnrawker hinted at the basic idea, and Jos pointed out some of the great examples of where general rules fail.

You need to look at the input and outputs of the code block and see how often something is actually happening.