Questions tagged [big-o-notation]

Question 1

So I understand that O is an upper bound and omega is a lower bound. I also understand that case is different than bounds, i.e worst case can have O/Theta/Omega different from best case. My question: ...

Question 2

There is the following algorithm: ...

Question 3

How does one go about proving that the lowest possible time complexity for traversing an array is $O(n)$?, it is easy to see that this is the case. But how could I formally prove that this is true?, ...

Question 4

Here's the problem: you get an array of numbers. lets say you get an array of 5 numbers: {5,3,4,1,1}. Each of the numbers in the array represent a 'tower'. Your goal is to make the array in the shape ...

Question 5

LeetCode Problem 347. Top K Frequent Elements asks the user to return a list of the $k$ most frequently occurring numbers from a list of numbers. The following solution uses bucket sort: ...

Question 6

I am reading Computer Science Distilled book and in section 2.2 The Big-O Notation there is a line. A function with fastest-growing term of $2^n$ or weaker is $O(2^n)$ What does weaker mean here? ...

Question 7

I haven't seen any estimation with big O of tangent, I tried to use limit for the proof, however for it's oscillating behaviour I find it hard to prove that $tan(x)\neq O(2^x)$ where x is all real ...

Question 8

$$ T(n) = \begin{cases} 4T(\frac n 2) + \Theta(n) & n \gt 1\\ 1 & n \le 1 \end{cases} $$ I have to calculate the complexity of an algorithm taking time according to above equations using ...

Question 9

I've been scouring around looking for a definition for Big-O when you have multiple input variables. For context, I'm an undergraduate student. Wikipedia mentions $$f(\mathbf{x})\text{ is }O(g(\mathbf{...

Question 10

The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/) Problem Statement You have an array, matchsticks, of size n, with ...

Question 11

I'm trying to devise an algorithm for the following prompt from LeetCode's daily challenge: You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[...

Question 12

I have initial condition $𝑛_1=2, 𝑣_1=1$, and the given recurrence relations: $𝑛_{𝑖+1}=2𝑛_𝑖,$ $𝑣_{𝑖+1}=2𝑣_𝑖+\frac{1}{2} 𝑛_𝑖$ I need to show that that, $v_i=\Theta(n_i\log⁡ n_i).$ I observe ...

Question 13

I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...

Question 14

I have for every constant $c$ (no matter how large) and for every $\epsilon >0$(no matter how small), how can I show that $$n.e^{\sqrt{\log n}}=\omega(n\log^c n)\\ n.e^{\sqrt{\log n}}=o(n^{1+\...

Question 15

To show $n\log n + n \log(\log n) = \Theta(\log n)$. Is this even correct? It can be easily shown that, $n \log n + n \log(\log n)$ is $O(n\log n)$ and also $\Omega(n\log n)$, with constants $2$ and $...

Stack Exchange Network

Questions tagged [big-o-notation]

Big O and Omega, how can they be different for a specific case(worst/best)

Complexity of Recursive Algorithm

Proving the lowest possible time complexity of traversing an array is $O(n)$

Algorithm for finding a 'mountain' with the tallest height in O(n) time

Why does the big-O for this algorithm not include k?

What does weaker term mean in the definition of BigO

Big O arithmetic of tangent

Calculating complexity for recursive functions with substitution method (Big O notation)

Confusion regarding Big-O definition with multiple variables

Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square

Graph Problem Time Complexity

Recurrence relation simplification

How to simplify $O(\log (n!))$?

Relationship between $\omega$ and o

Is $n\log n + n\log \log n = \Theta(\log n)$?

Hot Network Questions