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

248 questions
Filter by
Sorted by
Tagged with
160 views

### Finding largest elements

I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is ...
37 views

### Trouble with Big-O notation proof by definition

Let $a,b>0$. Prove $\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$. I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain ...
117 views

### Is it true that $2^{O(3k)} = 2^{O(k)}$?

Is it true that $2^{O(3k)} = 2^{O(k)}$? But It should be different from $O(2^{k}) = 2^{O(k)}$ ? I will be happy for simple explanation. Thanks.
4k views

### Time complexity $O(m+n)$ Vs $O(n)$

Consider this algorithm iterating over $2$ arrays $(A$ and $B)$ size of $A = n$ size of $B = m$ Please note that $m \leq n$ The algorithm is as follows ...
49 views

122 views

### How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?

Found this in solutions of a test as being true If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$. How does the above ...
18 views

### Comparisons of functions, their big-oh and their implications

I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true. If $f(n) = O(n^2)$ and $g(n) = O(n^2)$, then $f(n) = O(g(n))$. If $f(n) = O(g(n))$ and $g(n) = O(n^2)$, ...
49 views

### Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
41 views

84 views

### How can I find this code block's execution time t(n) and big O notation?

Hello I am a CSE student and this question was in my homework. ...
47 views

### Recurrence relations and induction: guessing the right bound

I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$ This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of T(n)=T(n-...
44 views

### Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
### What is the need for "some constant" times $n$?
I have a question regarding the following sentence: So we can make the following expressions: The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$ The worst case ...