Is the time complexity of the Oracle MAX function O(1), O(log n) or O(n) with respect to the number of rows in a table?

If you have a B-tree index on the column then finding the maximum value is O(log(n)) because the answer will be the last (or first) row of the index. Values are stored in the deepest nodes of the B-tree which has a height O(log(n)).

Without an index it is O(n) because all rows must be read to determine the maximum value.

Note: The O(n) notation ignores constants but in the real world these constants cannot be ignored. The difference between reading from disk and reading from memory is several orders of magnitude. Accessing the first value of an index is likely to be performed mostly in RAM, whereas a full table scan of a huge table will need to read mostly from disk.

Realistically, it's hard to say without specifying a query, a table definition, and a query plan.

If you have a table that has no index on the column you're computing the `MAX`

on, Oracle will have to do a full table scan. That is going to be O(n) since you've got to scan every block in the table. You can see that by looking at the query plan.

We'll generate a table with 100,000 rows and ensure that the rows are reasonably large using a `CHAR(1000)`

column

```
SQL> create table foo( col1 number, col2 char(1000) );
Table created.
SQL> insert into foo
2 select level, lpad('a',1000)
3 from dual
4 connect by level <= 100000;
100000 rows created.
```

Now, we can look at the plan for the basic `MAX`

operation. This is doing a full table scan (an O(n) operation)

```
SQL> set autotrace on;
SQL> select max(col1)
2 from foo;
MAX(COL1)
----------
100000
Execution Plan
----------------------------------------------------------
Plan hash value: 1342139204
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 13 | 4127 (1)| 00:00:50 |
| 1 | SORT AGGREGATE | | 1 | 13 | | |
| 2 | TABLE ACCESS FULL| FOO | 106K| 1350K| 4127 (1)| 00:00:50 |
---------------------------------------------------------------------------
Note
-----
- dynamic sampling used for this statement (level=2)
Statistics
----------------------------------------------------------
29 recursive calls
1 db block gets
14686 consistent gets
0 physical reads
176 redo size
527 bytes sent via SQL*Net to client
523 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
```

If you create an index on the column you're computing the `MAX`

of, Oracle can do a `MIN/MAX scan`

on the index. That is an O(log n) operation if that's the plan the optimizer chooses. Of course, as a practical matter, this is functionally an O(1) operation because the height of an index is never realistically going to exceed 4 or 5-- the constant terms here are going to dominate.

```
SQL> create index idx_foo_col1
2 on foo( col1 );
Index created.
SQL> select max(col1)
2 from foo;
MAX(COL1)
----------
100000
Execution Plan
----------------------------------------------------------
Plan hash value: 817909383
-------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 13 | 2 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 13 | | |
| 2 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 | 1 | 13 | 2 (0)| 00:00:01 |
-------------------------------------------------------------------------------------------
Note
-----
- dynamic sampling used for this statement (level=2)
Statistics
----------------------------------------------------------
5 recursive calls
0 db block gets
83 consistent gets
1 physical reads
0 redo size
527 bytes sent via SQL*Net to client
523 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
```

But then things get harder. Both `MIN`

and `MAX`

have the same O(log n) behavior individually. But if you have both `MIN`

and `MAX`

in the same query, suddenly you're back to an O(n) operation. Oracle (as of 11.2) hasn't implemented an option grab both the first block and the last block of an index

```
SQL> ed
Wrote file afiedt.buf
1 select min(col1), max(col1)
2* from foo
SQL> /
MIN(COL1) MAX(COL1)
---------- ----------
1 100000
Execution Plan
----------------------------------------------------------
Plan hash value: 1342139204
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 13 | 4127 (1)| 00:00:50 |
| 1 | SORT AGGREGATE | | 1 | 13 | | |
| 2 | TABLE ACCESS FULL| FOO | 106K| 1350K| 4127 (1)| 00:00:50 |
---------------------------------------------------------------------------
Note
-----
- dynamic sampling used for this statement (level=2)
Statistics
----------------------------------------------------------
4 recursive calls
0 db block gets
14542 consistent gets
0 physical reads
0 redo size
601 bytes sent via SQL*Net to client
523 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
```

Of course, in subsequent versions of Oracle, this optimization might be implemented and this would go back to being an O(log n) operation. Of course, you can also rewrite the query to get a different query plan that goes back to being O(log n)

```
SQL> ed
Wrote file afiedt.buf
1 select (select min(col1) from foo) min,
2 (select max(col1) from foo) max
3* from dual
SQL>
SQL> /
MIN MAX
---------- ----------
1 100000
Execution Plan
----------------------------------------------------------
Plan hash value: 3561244922
-------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 2 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 13 | | |
| 2 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 | 1 | 13 | 2 (0)| 00:00:01 |
| 3 | SORT AGGREGATE | | 1 | 13 | | |
| 4 | INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 | 1 | 13 | 2 (0)| 00:00:01 |
| 5 | FAST DUAL | | 1 | | 2 (0)| 00:00:01 |
-------------------------------------------------------------------------------------------
Note
-----
- dynamic sampling used for this statement (level=2)
Statistics
----------------------------------------------------------
7 recursive calls
0 db block gets
166 consistent gets
0 physical reads
0 redo size
589 bytes sent via SQL*Net to client
523 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
```

Similar Questions

What would be the Big O or Theta of a loop that runs forever? Just curious, was thinking about it today. Could you even bound it?

Most people with a degree in CS will certainly know what Big O stands for. It helps us to measure how (in)efficient an algorithm really is and if you know in what category the problem you are trying t

If a function body invokes 3 different functions, all of the order O(n), how do I calculate the order of the outer (containing) function? Yes, this is homework, and I've surprisingly failed to find a

I'm compiling own project. And it halted by this error: LINK||fatal error LNK1181: cannot open input file 'obj\win\release\src\lua\bindings.o'| Compiling using Code::Blocks with VS 2005/2008 compile

I'm just learning about Big O notation, and I've been going through a few thought puzzles, and I just thought I'd verify with people whether I'm thinking through things correctly. In Javascript would

What will be the Big O notation for the above complexity? Is it O(n)

We have 3 functions with big o notations: Func A: O(n) Func B: O(n^2) Func C: O(2^n) If these functions does n proccesses in 10 seconds, how much time need to proccess 2 * n processes for each functi

Can some help me with a function which is Big O(1) but not Ω(1) and the other way around? Some explanation would greatly help.

If I have an algorithm that takes 4n^2 + 7n moves to accomplish, what is it's O? O(4n^2)? O(n^2)? I know that 7n is cut off, but I don't know if I should keep n^2 coefficient or not. Thanks

Good afternoon all, We say that a hashtable has O(1) lookup (provided that we have the key), whereas a linked list has O(1) lookup for the next node (provided that we have a reference to the current n

I got an unknown algorithm that I need to calculate the time complexity for (Big O). The only thing that I know about the algorithm is how long it takes to finish its calculations for a given number o

I need to implement a key-value data structure that search for a unique key in O(lgn) or O(1) AND get max value in O(1). I am thinking about boost::bimap< unordered_set_of<key> ,multiset_of&

What are the space and time complexities, in Big O notation, for the Lempel-Ziv-Welch and Huffman compression algorithms? Google is failing me. Thanks, Francisco

I'm confused about how Big-O works when dealing with functions within functions (when analyzing worst case). For example, what if you have something like: for(int a = 0; a < n; a++) { *some functio

I really want to know real definition. I have tried to read a book but couldn't understood. O : Big-O notation worst case. Θ : Theta notation average case. Ω : Omega notation best case. Q1> But why

are there a limited amount of basic O Notations, considering you are meant to 'distil' them down to their most important part? O(n^2): O(n): O(1): O(log n) logarithmic O(n!) factorial O(na) polynomia

for (int j=0,k=0; j<n; j++) for (double m=1; m<n; m*=2) k++; I think it's O(n^2) but I'm not certain. I'm working on a practice problem and I have the following choices: O(n^2) O(2^n) O(n!) O(

Consider a question Which segment of abc.o contains function foo()? Is this the same question as What section of ELF contains this function foo()? Sorry .. i know this is very silly. I am a bit co

I'm having a hard time wrapping my head around the big-O notation for a pairing operation. The question is pretty simple- Generate all possible pairs for a given list of numbers in an array. My first

Find the big-O running time for each of these functions: T(n) = T(n - 2) + n ^2 Our Answers: n^2, n^3 T(n) = 3T(n/2) + n Our Answers: O(n log n), O(n^(log base 2 of 3)) T(n) = 2T(n/3) + n Our Ans

According to the definition of big O f(n) <= C*g(n)(which means f(n) = O(g(n)), it could be deduced that: f(n) <= C f(n) <= 2C I think there are no big differences between these two. What I

I always thought the complexity of: 1 + 2 + 3 + ... + n is O(n), and summing two n by n matrices would be O(n^2). But today I read from a textbook, by the formula for the sum of the first n integers,

I know there are quite a bunch of questions about big O notation, I have already checked Plain english explanation of Big O , Big O, how do you calculate/approximate it?, and Big O Notation Homework--

I am trying to understand what the Big O would be for the following method. for(Integer i : list){ if(list.contains(-i)) //doSomething } I know that the contains method is O(n) and that a for loop l

What Big-O notation would this fall under? I know setSearch() and removeAt() are of order O(n) (assume they are either way). I know without the for loop it'd be O(n), for certain, but I get confused h

sum = 0; for (i=0;i<n/2;i++) for (j=i; j<n/4; j++) sum++; What is the big O for the above code? I calculated the big O but I'm not sure if it's correct. This is my answer the outer loop will r

I have a counting algorithm for which I am trying to get a general big-o description. It is horribly nested and horribly exponential. Here it is: 1. For each T_i in T 2. For k = 1 to max_k 3. For eac

i <-- 1 while(i < n) j <--1 while(j < i) j <-- j * 2 i <-- i + 1 done My shot at this would be O(log n) for the inner loop. And I'm guessing the outer loop is O(n), for an overall c

Suppose an algorithm is known to be O(N2) and solving a problem of size M takes 5 minutes. About how long will it take to solve a problem of size 4M? Is it as simple as ... M=5min 4M=20min ?

I have written a function and I need to know the big O notation for it. I have tried to slove this myself and I get O(N^2), however I have been told that this is not the correct answer. Can someone pl

I have a few questions so please bear with me. I need some help to clarify Big O and run time. As I understand it Big O is a way of presenting the run time of an algorithm correct? From reading I've b

def foo(x): if x > 5: return foo(x–1) – foo(x-1) else: return 11 def bar(a,b): if (b > 0): return bar( bar(a, b+1) , b-1 ) else: return 0 How do I find the running time in Big O notation and ho

I am revising for an exam and I have found this problem on the internet and was wondering how I would go about solving it. (With base 2 logs) Prove that log(2n) is a member of O(log n). I have given

I have run across this method in our code base and wonder what the Big O is. The method takes a flat list and creates a tree, assigning the Parent and Children values as it goes. private void AddChild

We did an exercise in class today dealing with big-O notation. Here is one of the problems: void modifyArray(int a[], int size) { int max = a[0]; for (int i = 1; i < size / 2; ++i) { if (max < a

I am currently watching ocw video courses on Algorithms and in second lecture i stuck at a point where professor proves the following statement by induction:- n=O(1) proof:- For base case 1=O(1) supp

I'm testing out some functions I made and I am trying to figure out the time complexity. My problem is that even after reading up on some articles on Big O I can't figure out what the following should

I am trying to find the Big O for this code fragment: for (j = 0; j < Math.pow(n,0.5); j++ ) { /* some constant operations */ } Since the loop runs for √n times, I am assuming this for-loop is O(√

If I had a function like this: void myfunction(node* root) { for(int i = 0; i<root->children.size();i++) { myfunction(root->children[i]); } } Would that be Big O of n^2 or Big O of n? If you

i have big pool of core date objects (around 10000) and there is too long time doing code according profile: NSDate *maxExternalChangedDate = [codes valueForKeyPath:@@max.externalChangedDate]; is co

is there a max function in c so i can do something like this to calculate tree height :or perhaps there is a better way to calculate tree height. int height(struct node *tree) { if (tree == NULL) retu

So, I really don't get Big O notation. I have been tasked with determining O value for this code segment. for (int count =1; count < n; count++) // Runs n times, so linear, or O(N) { int count2

For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time. Can anybody please tell me if I'm on the right track? //Fragment 1 for(int i = 0;

Brief: When academic (computer science) papers say O(polylog(n)), what do they mean? I'm not confused by the Big-Oh notation, which I'm very familiar with, but rather by the function polylog(n). T

When storing a binary blob of data in keychain for security reasons, what is considered a big blob of data? 1kB? 1MB? How big a blob of binary data can you store in keychain (without running into pe

How can I represent the complexity of std::find_end algorithm as Big-O notation? The complexity of std::find_end is defined as follows: At most (last2 - first2) * (last1 - first1 - (last2 - first2) +

How to prove this: x^7 = O(x^10) x^10 = O(x^7)? ı couldnt prove this statement.

I have the following question: Solve the recurrence relation simplifying the answer using Big 'O' notation: f(0) = 2 f(n) = 6f(n-1)-5, n>0 I know this is a first order inhomogenous recurrence rela

I'm trying to understand a particular aspect of Big O analysis in the context of running programs on a PC. Suppose I have an algorithm that has a performance of O(n + 2). Here if n gets really large t

I'm trying to rate the efficiency of a function where the input is an array of strings. The algorithm always iterates through every item in this array. This strings contained in this array are of vari