You need to search through every element in the heap in order to determine if an element is inside.

One optimization is possible, though (we assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don’t need to search further from that node. However, even with this optimization, search is still O(N) (need to check N/2 nodes in average).

### Related Contents:

- How can building a heap be O(n) time complexity?
- Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
- Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
- How to delete in a heap data structure?
- Why is O(n) better than O( nlog(n) )?
- Computing set intersection in linear time?
- How to implement a queue using two stacks?
- What is the difference between tree depth and height?
- Is log(n!) = Θ(n·log(n))?
- Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
- Find running median from a stream of integers
- What exactly does big Ө notation represent?
- Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)? [closed]
- Are 2^n and n*2^n in the same time complexity?
- How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
- What is the advantage to using Bloom filters?
- Can hash tables really be O(1)?
- design a stack such that getMinimum( ) should be O(1)
- What is pseudopolynomial time? How does it differ from polynomial time?
- Find kth smallest element in a binary search tree in Optimum way
- Time complexity of Euclid’s Algorithm
- Check if two linked lists merge. If so, where?
- Most efficient way to store thousand telephone numbers
- Worst case in Max-Heapify – How do you get 2n/3?
- Why are Fibonacci numbers significant in computer science?
- Difference between back tracking and dynamic programming
- B-tree faster than AVL or RedBlack-Tree? [closed]
- Which is better: O(n log n) or O(n^2)
- Javascript data structures library [closed]
- Why is the constant always dropped from big O analysis?
- How does 3D collision / object detection work?
- Good algorithm and data structure for looking up words with missing letters?
- Why in a heap implemented by array the index 0 is left unused?
- What is the runtime complexity of a switch statement?
- Algorithm/Data Structure Design Interview Questions [closed]
- Why is the Big-O complexity of this algorithm O(n^2)?
- Quicksort superiority over Heap Sort
- Mastering Recursive Programming [closed]
- How do I find the median of numbers in linear time using heaps?
- Hashing a Tree Structure
- Applications of red-black trees
- Which data structures and algorithms book should I buy? [closed]
- find the max difference between j and i indices such that j > i and a[j] > a[i] in O(n)
- Big O notation Log Base 2 or Log Base 10 [duplicate]
- What is the Big O analysis of this algorithm?
- Why use binary search if there’s ternary search?
- Algorithm for detecting “clusters” of dots [closed]
- Example of Big O of 2^n
- How to apply binary search O(log n) on a sorted linked list?
- Why are hash table expansions usually done by doubling the size?