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