オーダ表記での速度の計算

Question

前提・実現したいこと

長さNの正整数列A=(A1,A2,…,AN)とQ個のクエリが与えられます。
i(1≤i≤Q)番目のクエリでは、正整数 Kiが与えられるので、A1,A2,…,ANのいずれとも異なる正整数のうち、小さい方から数えてKi番目のものを求めてください。

という競技プログラミングの問題に自分が解いたコードが下記コードなのですが、こちらのアルゴルズムの速度はオーダ表記でどれだけになりますか？

発生している問題・エラーメッセージ

該当のソースコード

#include<stdio.h>
int main(void){
  int N, Q;
  scanf("%d%d", &N, &Q);
  int i, A[N], K[Q];
  A[0]=0;
  for(i = 1 ; i <= N ; i++){
    scanf("%d", &A[i]);
  }
  for(i = 0 ; i < Q ; i++){
    scanf("%d", &K[i]);
  }
  int c = 0, k, l;
  for(i = 0 ; i < Q ; i++){
    c = 0;
    l = 0;
    k = 1;
    while(1){
      c+=1;
      if(A[k] == c){
	l+=1;
	k++;
      }
      if(K[i] == c-l){
	printf("%d\n", c);
	break;
      }
    }
  }
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

O(Qmax・Kmax)、Qの最大値がKのそれに対して十分小さいのであればO(n)とみなしても大差ないですし
無視できない程であればO(n^2)です。

ところで

if(A[k] == c){
l+=1;
k++;
}

この後にlを使っていませんので意味がありません
また、A[i]が昇順に並んでいる事を期待しているのも問題かもしれません。

---

この問題の場合、「小さい方からKi番目の正整数」=「Ki」であり
そこから、Aj(j=1～N)のいずれとも異なる正整数のうち「小さい方からKi番目」とは何かを考えたほうがよいですね

Answer 2

ループのネスティングだけであれば、一重ループでO(n)、二重ループでO(n^2)、以下同じ。

Answer 3

何回ループ回して計算してるのかを数えればいいです。

あなたの組んだコードなら、あなたがわかるんでは

Answer 4

アルゴリズムの計算量をランダウの記法で表すことはありますが、レジスタやメモリの制約のある計算プログラムの計算量をランダウの記法で表すことはないと思います。

raiboz1115さんのアルゴリズムの計算量をランダウの記法で表すことはできません。
敢えて書くならO(∞)ですが、そういう書き方はありませんので、どのような関数f(N,Q)を使ってもO(f(N,Q))にはならないという方が正確でしょう。

このような問題の計算量を評価するときにはデータが何であれ、NなりQなりによって決る計算量の上限は何かをランダウの記法で表すのですが、raiboz1115さんのアルゴリズムの場合、N=1、Q=1であっても、K1が大きくなると計算量はどんどん大きくなります。
従ってどのような関数f(N,Q)を使ってもO(f(N,Q))を満たすことはできません。