Questions tagged [big-o-notation]
Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation.
9
questions
5
votes
1answer
89 views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
1
vote
2answers
51 views
Algorithms: Determining Asymptotic Notation from a given execution time
I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it.
Question 1: An Algorithm with ...
4
votes
1answer
700 views
What does $|V|=O(|E|)$ mean?
I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
2
votes
5answers
473 views
Big O notation for Average case in Linear search
Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
2
votes
1answer
118 views
How to compare n number of m-dimensional points among one another with minimum time complexity?
Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
2
votes
2answers
78 views
How to determine time complexity with a simple way?
I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−...
1
vote
2answers
109 views
Solving unusual recurrence with two variables
I have the following recurrence relation:
$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$
With the following base cases (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$...
1
vote
3answers
1k views
Why is heap insert O(logN) instead O(n) when you use an array?
I am studying about the arrays vs heap for make a priority queue
For check the heap implementation I am reviewing this code: Heap
, but I have the following question.
Heap is based on array, and ...
0
votes
0answers
66 views
Balanced vs Unbalanced KD-tree range search/query complexity
I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree.
I see all these different articles where the same the complexity is O(sqrt(N)) where N is the ...
