# 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, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
86 views

### What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
• 356
106 views

### Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
1 vote
91 views

1 vote
42 views

42 views

### Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
• 101
105 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
• 183
114 views

57 views

### Trying to understand the time complexity of IDDFS

I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out. For BFS it is ...
48 views

### Basic Clique Complexity Question

A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
75 views

### Derive complexity from recurrence relation

On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated: $T(n) = 3 T(\frac{n}{2}) + cn + d$ And then, by invocation of ...
• 241
49 views

### Can 0 be a tight upper bound of -4n?

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2). We can take it ...
92 views

### What is the asymptotic runtime of the below equation?

What is the asymptotic of ${n \choose 3} \log ^4n$ ? I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?
• 135
442 views

### Is reduction from Rudrata/Hamiltonian path to Rudrata/Hamiltonian cycle O(1)?

I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
85 views

### Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$

Lets define function $T(n)$ as \begin{align*} T(1) &= T(2) = 1\\ T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\ \end{align*} Does $T(n)=O(\log(n))$? I have no idea how to ...
108 views

### Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n? I tried to write this in python to ...
• 81
80 views

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)... 0 votes 0 answers 36 views ### The following time complexity is right for the given algorirthm Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ... 0 votes 0 answers 2k views ### Time complexity for computing the highest degree vertex Consider an undirected and unweighted graph with$n=|V|$nodes and$m=|E|$edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ... • 101 0 votes 0 answers 52 views ### Time complexity about Maximum subarray I recently came across a function called the strawman algorithm which the pseudo code looks like this: ... • 101 0 votes 0 answers 52 views ### Big$O$approximation for$T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$I have the following complexity equation:$T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$with the base case$T(m)=1$. Is it possible to calculate a big$O$approximation for such equation? What is the right ... 0 votes 0 answers 35 views ### Big O notation of$\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$What is the O-notation (or$\Theta$notation ) of$\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$? Can I use Sterling approximation :$n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$... 0 votes 0 answers 19 views ### Question in regards to how an O(N^3) looks like using while/for loops would the code below be considered O(N^3)? while (...) { while (...) { } while (...) { } } 0 votes 0 answers 1k views ### What is the Big theta of$(\log n)^2+2n+4n+\log n + 50$?$f(n)=(\log n)^2+2n+4n+\log n + 50$I am trying to mathematically prove that$f(n)$falls under some time complexity big theta. My guess is that it is$(\log n)^2$because it is the dominant term. I ... • 101 0 votes 0 answers 67 views ### Summing big-O-notation prove or disprove $$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$ I have no idea about where to begin. what are the theories which should be used here? 0 votes 0 answers 140 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 ... 0 votes 0 answers 37 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 ... 0 votes 2 answers 128 views ### How to show working for summing of Big O notation The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$ • 123 -1 votes 3 answers 125 views ### Time complexity of algorithm involving function calls Me again. This time I have a more general question. Suppose I have the following code snippet: ... • 175 -1 votes 2 answers 158 views ### How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows? f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n)) I think we can prove this for omega but how can we prove it for Big oh ? because if we simplify it to logn + logn <= logn +5 => logn<=... -1 votes 2 answers 364 views ### what is the time complexity of this while loop nested in a for loop? I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length: ... • 1 -1 votes 1 answer 88 views ### How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method? Suppose you have to prove the solution to the following recurrence by Induction, $$T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases}$$ Here,$\...
• 179
I built a recursion tree like this: 0 / \ 0 0 /\ /\ ... ... So the tree has height n, and width $2^n$. But if the sum of all levels is \$\sum_{i=0}^{n}...