1. compute statistics on table ALWAYS compute statistics on INDEXES
2. in 8i and higher estimate statistics on table ALWAYS estimate statistics on INDEXES.

U may check it (it simple):

SQL> analyze table emps delete statistics;

Table analyzed.

SQL> analyze table emps compute statistics;

Table analyzed.

SQL> select index_name, sample_size, last_analyzed from user_indexes where table_name = 'EMPS';

INDEX_NAME SAMPLE_SIZE LAST_ANAL
------------------------------ ----------- ---------
EMPS_PK 0 16-AUG-02
IDX_DEP_ID_EMP 0 16-AUG-02
IDX_FIRST_NAME 0 16-AUG-02
IDX_JOB_ID_EMP 0 16-AUG-02
IDX_U_LAST_NAME 0 16-AUG-02

SQL> analyze table emps delete statistics;

Table analyzed.

SQL> analyze table emps estimate statistics sample 30 percent;

Table analyzed.

SQL> select index_name, sample_size, last_analyzed from user_indexes where table_name = 'EMPS';

INDEX_NAME SAMPLE_SIZE LAST_ANAL
------------------------------ ----------- ---------
EMPS_PK 30 16-AUG-02
IDX_DEP_ID_EMP 30 16-AUG-02
IDX_FIRST_NAME 30 16-AUG-02
IDX_JOB_ID_EMP 30 16-AUG-02
IDX_U_LAST_NAME 30 16-AUG-02

SQL> select index_name, sample_size, last_analyzed from user_indexes where table_name = 'EMPS';

In first case we had SAMPLE_SIZE = 0 (compute statistics)
In second we had SAMPLE_SIZE = 30 (estimate statistics (30%))