[split] Linked list question

>a.) You mean square root of N?
Assuming you're talking about my "O(# of powers of 2 below n)" estimate, no, I really do mean powers of 2. The square root of N is close at first (but not quite right), and it gets worse as N grows.

>f.) As far as I understand... shouldn't it be O(N*N^3) = O(N^4)?
Let's take a look:

for( i = 0; i < n; i++) {
  for( j = 0; j < n * n; j++) {
    for( k = 0; k < j; k++)
      count++;
  }
}

The i loop is O(N), no need to explain why. ;) The j loop is O(N^2) as explained earlier in the thread. The k loop is an instance of taking the upper bound. To get the complexity of the k loop, you choose the largest value that k would reach before the loop ends, which in this case would be the j loop's upper bound: n*n.

So, you've got an O(N^2) loop inside another O(N^2) loop inside an O(N) loop. The k loop isn't quadratic the whole time, but that's the upper bound, so we'll call it O(N^2). Put it all together and you get O(N^5).

>g.) And this one... O(N^4) as well?

for ( i = 0; i < n * n; i++) {
  for (j = 0; j < i; j++) {
    for ( k = 0; k < j; k++)
      count++;
  }
}

The i loop is quadratic, the j loop depends on i and thus is also quadratic, and the k loop depends on j which makes it quadratic too. Two times four is six, so O(N^6)... Your algorithms keep getting slower. ;)

You'll notice that much of the time in these algorithms, the inner loops aren't quadratic. A lot of time is spent on the lower ranges and will be much faster than the Big O complexity suggests. While it's possible to refine the complexity to something more accurate, in my experience it's not really worth it.

Aaaahhh... xD How could I miss?... Oh well... :) Must keep in mind that I'm still learning.

Thanks! I got stuck on another thing - which has nothing to do with the Big Oh notations though. And this one - I swear - I could scratch my head bald before I figure out how to fix it... I've been reading for HOURS literally in the book - but I can't understand it!

It's solving polynomials with LinkedLists...
here's one of the things I was working on. Pleeease enlighten me! The final exam is tomorrow and I did everything I could to fix this. :(

A polynomial can be represented by a sorted linked list
public class Polynomial {
private SortedLinkedList<Term> poly;
//constructors and other methods
}

Where the Term defines the representation of the polynomial term:
public class Term implements Comparable<Term> {
private double coeff; //Coefficient
private int exp; //exponent
//and then follow constructors and accessor methods
}

For example
p(x) = 10x^100 + 5x^20 + 3x + 10
xp(x) = 10x^101 + 5x^21 + 3x^2 + 10x

Write a static method for the class Polynomial to the polynomial multiplication by x:
public static Polynomial xPolynomial( Polynomial p )

Tip: Followings are some public methods provided by these methods

LinkedList

/***************************** PUBLIC OPERATIONS *****************************
* boolean isEmpty()		--> Return true if empty; else false
* LinkedListIterator zeroth()	--> Return position to prior to first
* LinkedListIterator first()	--> Return first position
* void insert(x, p)		--> Insert x after current iterator position p
*******************************************************************************/

SortedLinkedList:
//void insert(x)			--> Insert x
//void insert(x, p)		--> Insert x (ignore p)

LinkedListIterator:
//void advance()			--> Advance
//boolean isValid()		--> True if at valid position in list
//AnyType retrieve()		--> Return item in current position