# 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.

68 questions
Filter by
Sorted by
Tagged with
78 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 ...
67 views

### Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$? I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
115 views

### Is O(n log n) exponential speedup over O(n^2)?

I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
99 views

161 views

### How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

I understand that essentially we have to prove that $$c_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c_2(n^2\log n)\,.$$ I am confused on how to simplify this further? And ...
34 views

I was reading a research paper and there I read the following: $t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\... 2answers 83 views ### How to find i-th root of n whose remainder is the smallest? Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ... 0answers 28 views ### How to find running time complexity of divide and conquer method without Master Theorem I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of$T(n) = aT(\frac{n}{b}) + n^clog^k(n)$The reason behind it has to do with drawing a tree ... 0answers 23 views ### Asymptotics and logarithms/exponents We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ... 3answers 299 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 ... 1answer 74 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 ... 1answer 19 views ### Asymptotic Relationship from Limit F(n) = n-100 G(n) = n-200 I am trying to show the asymptotic relationship between these two functions using limits. I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c. ... 1answer 29 views ### Help with Big-O homework [duplicate] "er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct. 1answer 44 views ### Helping prove this notation for Big-O(n!) Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is ... 2answers 107 views ### Big-O Notation and Calculus? I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ... 1answer 592 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 ... 2answers 58 views ### Struggling to understand the symbolism around the big oh formal definition I'm struggling to understand what exactly T(n), and f(n) is in the above text: When we compute the time complexity T(n) of an ... 1answer 54 views ### Time complexity, Big-O for this function? def f(n): if n < 100000: return 0; for(int i = 0; i < n*n; i++){ return f(n-1) } What is the time complexity? My answer is$O((...
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
### How to calculate Big O of $T(n) = aT(n^b) + f(n)$?
I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or $O(n^{\log_b{a}} + f(n))$ Today I was faced with \$T(n) = T(\sqrt n)...