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

286 questions
Filter by
Sorted by
Tagged with
26 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 vote
3k views

### Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
1 vote
36 views

### Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
18 views

### Landau Notation/Big O notation

In our class the following exercises/examples were given: Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that: $n^{2/3} \in \Omega(log^8(n))$. Then in the Solution ...
1 vote
26 views

### Are there any "fast" algorithms for defragmenting memory?

This is about memory, not files or filesystems. So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later ...
30 views

### Whats the big O notation of the following code?

int j , f; System.out.println("enter a number"); ...
59 views

31 views

### Baby step giant step algorithm complexity calculation

My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
42 views

### Big O- and Omega-Notation for functions

I want to find out how to check, if the following relationships are true or false. f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false; f(n) = 3n^2; g(n) = 9^...
73 views

### Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
1 vote
26 views

### Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
1 vote
93 views

### Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
58 views

### Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
125 views

### Prove big O notation for $\log(n!)$ without applying Stirling's formula

I want to prove that, $$\log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$ The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow. Can ...
95 views

### Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?

I'm following an online course about Complexity and I'm learning a lot of stuff. I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here. ...
45 views

### sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
39 views

70 views

### Does $f(n) \in O(g(n))$ imply $2^{f(n)} \in O(2^{g(n)})$?

Is the following true: $$f(n) \in O(g(n)) \text{ then } 2 ^ {f(n)} \in O(2^{g(n)})$$
96 views

### $\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true: \log_{2}{\left(\frac{1}{2}n\right)} + \log_{2}{\left(\frac{1}{4}n\right)}...
93 views

### best and worst case number of key comparisons of an algorithm

Consider the following algorithm: ...
378 views

### Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
1 vote
84 views

### Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
1 vote
### Whether and how to distinguish two kinds of $O(1)$ speedup
Here is a very bad algorithm that computes $4n$ for an integer input. ...